题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1269
一道判断强连通图的裸题,强连通图就是图中任意两点之间可以相互到达,直接用tarjan写就好了,直接求强连通分量,等于1就是Yes。
AC代码:
#include <bits/stdc++.h>
#define maxn 10005
#define maxm 100005
using namespace std;
struct Node{
int to,next;
}Edge[maxm];
int head[maxn], num;
int dfn[maxn], low[maxn], cnt;
bool vis[maxn], flag;
int n, m, tot;
void init(){
for(int i=0;i<=n;i++){
low[i] = dfn[i] = 0;
head[i] = -1;
vis[i] = false;
}
flag = true;
num = cnt = tot = 0;
}
void add(int u,int v){
Edge[num].to = v;
Edge[num].next = head[u];
head[u] = num ++;
}
void tarjan(int x){
dfn[x] = low[x] = ++ cnt;
vis[x] = true;
for(int i=head[x];i!=-1;i=Edge[i].next){
int to = Edge[i].to;
if(!dfn[to]){
tarjan(to);
low[x] = min(low[x], low[to]);
}
else if(vis[to]){
low[x] = min(low[x], dfn[to]);
}
}
if(low[x] == dfn[x]){
tot ++;
}
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n == 0 && m == 0) break;
init();
for(int i=0;i<m;i++){
int u, v;
scanf("%d%d",&u, &v);
add(u, v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
if(tot == 1) puts("Yes");
else puts("No");
}
return 0;
}