• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# POJ 2186

2周前 (05-03) 6次浏览

Tarjan之前做一道leetcode的时候刷过，这次在OJ上找找感觉。

``````#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;

const int maxn= 1e4+5;
const int maxm= 5e4+5;

vector<int> G[maxn];
int belong[maxn], num[maxn];
bool ins[maxn];
int dfn[maxn], low[maxn], dg[maxn];
int scc, tm, top;
int S[maxn];

void Tarjan(int u)
{
low[u]= dfn[u]= ++tm;
S[++top]= u;
ins[u]= 1;
int n_eg= G[u].size();
for (int i= 0; i< n_eg; ++i){
int v= G[u][i];
if (!dfn[v]){
Tarjan(v);
if (low[v]< low[u]){
low[u]= low[v];
}
}
else if (ins[v] && dfn[v] < low[u]){
low[u]= dfn[v];
}
}
if (dfn[u]== low[u]){
int v;
dg[scc]= num[scc]= 0;
do{
v= S[top--];
ins[v]= 0;
belong[v]= scc;
++num[scc];
}while(v!= u);
++scc;
}
}
int solve(const int n)
{
for (int i= 1; i<= n; ++i){
dfn[i]= 0;
ins[i]= 0;
}
tm= scc= 0;
top= -1;
for (int i= 1; i<= n; ++i){
if (!dfn[i]){
Tarjan(i);
}
}

for (int i= 1; i<= n; ++i){
int n_eg= G[i].size();
for (int j= 0; j< n_eg; ++j){
int v= G[i][j];
if (belong[i]!= belong[v]){
++dg[belong[i]];
}
}
}

int ck= 1, ans= 0;
for (int i= 0; i< scc; ++i){
if (!dg[i]){
--ck;
ans= num[i];
}
}

if (ck< 0){
ans= 0;
}
else if (ck){
ans= n;
}

return ans;
}

int main(int argc, char const *argv[])
{
int n, m;
int f, t;
scanf("%d %d", &n, &m);

for (int i= 0; i< m; ++i){
scanf("%d %d", &f, &t);
G[f].push_back(t);
}

printf("%dn", solve(n));
return 0;
}
``````