思路：tarjan算法求强连通分量
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; const int maxn = 10005; int n, m; vector mp[maxn]; int dfn[maxn]; int low[maxn]; int vis[maxn]; int in_stack[maxn]; int index; int color[maxn]; int col; bool color_is_ok[maxn]; stack s; int sum; void tarjan(int u) {//tarjan求强连通分量 dfn[u] = low[u] = ++ index; s.push(u); in_stack[u] = 1; vis[u] = 1; sum ++; int d = mp[u].size(); for(int i = 0; i < d; i ++) { int v = mp[u][i]; if(!vis[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if(in_stack[v]) { low[u] = min(low[u], dfn[v]); } } if(dfn[u] == low[u]) {//每求到一个强连通分量然后将这个强连通分量染色 int v; do { v = s.top(); s.pop(); in_stack[v] = 0; color[v] = col; } while(u != v); col ++;//为了区分每个强连通分量 } } int main() { while(scanf(%d %d, &n, &m) != EOF) { for(int i = 0; i <= n; i ++) { mp[i].clear(); } int u, v; for(int i = 0; i < m; i ++) { scanf(%d %d, &u, &v); mp[u].push_back(v); } memset(vis, 0, sizeof(vis)); memset(in_stack, 0, sizeof(in_stack)); memset(color, 0, sizeof(color)); index = 0; col = 1; sum = 0; for(int i = 1; i <= n; i ++) { if(!vis[i]) tarjan(i); } // cout << sum << endl; if(sum != n) { printf(0 ); continue; } // for(int i = 1; i <= n; i ++) cout << color[i] << ; // cout << endl; //标记有多少个缩点后出度为0的强连通分量 memset(color_is_ok, true, sizeof(color_is_ok)); for(int i = 1; i <= n; i ++) { int d = mp[i].size(); for(int j = 0; j < d; j ++) { if(color[mp[i][j]] != color[i]) { color_is_ok[color[i]] = false; break; } } } // for(int i = 1; i < col; i ++) { // cout << color_is_ok[i] << ; // } // cout << endl; int ans_col; int cnt = 0; for(int i = 1; i < col; i ++) { if(color_is_ok[i]) { ans_col = i; cnt ++; } } if(cnt == 1) {//当且仅当只有一个强连通分量构成的缩点出度为0时有答案 int ans = 0; for(int i = 1; i <= n; i ++) { if(color[i] == ans_col) { ans ++; } } printf(%d , ans); } else { printf(0 ); } } return 0; }
?