题目链接：
方法：就是求强连通分支个数，为1就可以。
感想：《算法导论》上额强连通分支部分的定理证明有必要多理解。
代码：
View Code #include#include using namespace std;//int const MAX =0x3f3f3f3f;int const MAX = 10005;struct Arc{ int vetex; Arc* nexttArc;};struct Node{ int x; Arc* firstArc;};Node* o_nodes[MAX];Node* r_nodes[MAX];bool visited[MAX];int n,m;void createArc(int x,int y,bool inO){ Arc* arc = (Arc*)(malloc(sizeof(Arc))); arc->vetex = y; if(inO) { if(o_nodes[x]->firstArc == NULL) arc->nexttArc=NULL; else arc->nexttArc=o_nodes[x]->firstArc; o_nodes[x]->firstArc = arc; } else { if(r_nodes[x]->firstArc == NULL) arc->nexttArc=NULL; else arc->nexttArc=r_nodes[x]->firstArc; r_nodes[x]->firstArc = arc; }}void loadArc(int x,int y){ createArc(x,y,true); createArc(y,x,false);}int last = 0,traversedCount=0;void DFS(int root,bool inO=true){ Arc* t_arc; if(inO) t_arc = o_nodes[root]->firstArc; else t_arc = r_nodes[root]->firstArc; if(!visited[root] && !inO) traversedCount++; visited[root] = true; while(t_arc!=NULL) { if(!visited[t_arc->vetex]) DFS(t_arc->vetex,inO); t_arc = t_arc->nexttArc; } last = root; }int main(){ while(scanf("%d %d",&n,&m) && !(n==0 && m==0)) { memset(visited,false,sizeof(visited)); last = 0; traversedCount = 0; for(int i=1;i<=n;i++) { o_nodes[i] = (Node*)malloc(sizeof(Node)); r_nodes[i] = (Node*)malloc(sizeof(Node)); o_nodes[i]->firstArc = NULL; r_nodes[i]->firstArc = NULL; } int i = 1; int a,b; while(i<=m) { scanf("%d %d",&a,&b); loadArc(a,b); i++; } int count = 0; bool valid = true; for(i=1;i<=n;i++) { if(visited[i] == false) { if(count>0) { valid = false; break; } else { DFS(i,true); count++; } } } if(!valid) cout<<"No"<