HDU-1269（Tarjan模板-求强连通分量）
题目连接
题意：
求一个有向图n个点 m 条边，是否是强连通分量，如果是输出Yes, 不是输出No.
数据范围
n < 10000, m < 100000
思路：
Tarjan模板题
补习：
AC code:
/*
Tarjan求有向图的强连通分量，
*/
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 1e5 + 10;
struct Edge{
int to, next, dis;
}edge[MAXN << 1];
int head[MAXN], cnt, ans;
bool vis[MAXN];
//dfn 第一次访问到该节点的时间（时间戳）
//low[i] low[i]能从哪个点（最早时间戳）到达这个点的。
int dfn[MAXN], low[MAXN], tot;
stack stc;
void add_edge(int u, int v, int dis) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
void Tarjan(int x) {
dfn[x] = low[x] = ++tot;
stc.push(x);
vis[x] = 1;
for(int i = head[x]; i; 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]);
}
}
//cout << x << " " << low[x] << " " << dfn[x] << endl;
if(low[x] == dfn[x]) { //发现是整个强连通分量子树里 的最小根。
//int cnt = 0;
ans++; //强连通分量计数器
while(1) {
int top = stc.top();
stc.pop();
//cnt ++;
vis[top] = 0;
//cout << top <> n >> m && (n || m)){
init();
int x, y;
for(int i = 1; i > x >> y;
add_edge(x, y, 0); //有向图求强连通
}
for(int i = 1; i <= n; ++i) {
if( !dfn[i] )
Tarjan(i);
}
if(ans == 1) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
作者：Harington
