邻接表|全联通|hdu 1269

#include<stdio.h>
#include<iostream>
#include<malloc.h>
#define maxn 10000+5
using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}*List,LNode;

List LinkList[maxn];
int visit[maxn];
int stack[maxn];
int dfn[maxn];
int low[maxn];
int cnt;
int deep;
int flag;
int sn;

void addNode(List &p,int d_) {
    List q=(List)malloc(sizeof(LNode));
    q->data = d_;
    q->next = p-> next;
    p->next = q;

}


void displayNode(List &p) {
    List q=(List)malloc(sizeof(LNode));
    q = p->next;
    while(q!=NULL) {
        cout<<q->data<<"->";
        q=q->next;
    }
}
void DFS(int v) {
    List  p = LinkList[v]->next;
    deep++;
    visit[v]=1;
    stack[++sn] = v;
    dfn[v] = low[v] = deep;

    while(p!=NULL) {

        int u= p->data;
        if(visit[u]==0) {
            DFS(u);
            low[v]=(low[v]<low[u])?low[v]:low[u];
            if(flag) return;
        } else
            low[v]=(low[v]<dfn[u])?low[v]:dfn[u];
        p = p->next;
    }

    if(low[v]==dfn[v]) {
        //表示在栈中的当前点到栈顶的顶组成一个强连通
        if(v!=1)
            flag=1;
    }
}
    int main() {
        int n,m;//n个房间 m条边
        int v,u;
        while(scanf("%d%d",&n,&m)>0&&n+m!=0) {
            //建立结点
            for(int i=1; i<=n; i++) {
                LinkList[i] = (List)malloc(sizeof(LNode));
                visit[i]=0;//设置未访问
                LinkList[i]->next=NULL;//邻接为NULL
            }

            while(m--) {
                scanf("%d%d",&v,&u);
                addNode(LinkList[v],u);
            }

            for(int i=1; i<=n; i++) {
                cout<<"NODE "<<i<<"->";
                displayNode(LinkList[i]);
                cout<<endl;
            }
            flag=0;
            deep = 0;
            sn=0;
            DFS(1);
            if(flag)printf("No\n");
            else printf("Yes\n"); 
        }
        
        return 0;
    }