A - Network of Schools POJ - 1236强连通分量缩点

xiaoxiao2021-02-28  82

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> #include <vector> #include <stack> using namespace std; int n, m; vector<int> g[101]; bool flag[101]; int dfn[101], f[101], low[101]; int cnt, N; stack<int> s; void tarjan(int u) { dfn[u] = low[u] = ++cnt; flag[u] = true; s.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (flag[v] && dfn[v] < low[u]) low[u] = dfn[v]; } if (low[u] == dfn[u]) { N++; int v; do { v = s.top(); s.pop(); flag[v] = false; f[v] = N; } while (u != v); } } int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) g[i].clear(); for (int x, i = 1; i <= n; i++) while (scanf("%d", &x), x) g[i].push_back(x); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); cnt = 0, N = 0; for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); if (N == 1) { printf("1\n0\n"); continue; } int in[101] = {0}, out[101] = {0}; for (int i = 1; i <= n; i++) for (int j = 0; j < g[i].size(); j++) if (f[i] != f[g[i][j]]) { in[f[i]]++; out[f[g[i][j]]]++; } int x = 0, y = 0; for (int i = 1; i <= N; i++) { if (!in[i]) x++; if (!out[i]) y++; } printf("%d\n%d\n", y, max(x, y)); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-72209.html

最新回复(0)