[USACO5.3]校园网Network of Schools

 1 #include <bits/stdc++.h> 2 ?3 using namespace std; 4 ?5 #define re register 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i) 7 #define repd(i, a, b) for (re int i = a; i >= b; --i) 8 #define maxx(a, b) a = max(a, b); 9 #define minn(a, b) a = min(a, b);10 #define LL long long11 #define inf (1 << 30)12 13 inline int read() {14 ????int w = 0, f = 1; char c = getchar();15 ????while (!isdigit(c)) f = c == ‘-‘ ? -1 : f, c = getchar();16 ????while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ ‘0‘), c = getchar();17 ????return w * f;18 }19 20 const int maxn = 100 + 5;21 22 vector<int> G[maxn];23 int pre[maxn], low[maxn], dfs_clock = 0, sccno[maxn], sc = 0;24 stack<int> s;25 26 void dfs(int u) {27 ????pre[u] = low[u] = ++dfs_clock;28 ????s.push(u);29 ????for (register int i = 0; i < G[u].size(); ++i) {30 ????????register int v = G[u][i];31 ????????if (!pre[v]) {32 ????????????dfs(v);33 ????????????minn(low[u], low[v]);34 ????????} else35 ????????if (!sccno[v]) minn(low[u], pre[v]);36 ????}37 ????if (pre[u] == low[u]) {38 ????????sc++; int x = 0;39 ????????while (x != u) {40 ????????????x = s.top(); s.pop();41 ????????????sccno[x] = sc;42 ????????}43 ????}44 }45 46 int n, b[maxn];47 48 int main() {49 ????n = read();50 51 ????rep(i, 1, n) {52 ????????int x;53 ????????while (x = read()) G[i].push_back(x);54 ????}55 56 ????rep(i, 1, n)57 ????????if (!sccno[i]) dfs(i);58 59 ????int ans = 0;60 ????if (sc != 1) {61 ????????rep(i, 1, n)62 ????????????for (register int j = 0; j < G[i].size(); ++j)63 ????????????????if (sccno[i] != sccno[G[i][j]]) b[sccno[i]] = 1;64 ????????rep(i, 1, sc) if (!b[i]) ans++;65 ????????memset(b, 0, sizeof(b));66 ????????int ans1 = 0;67 ????????rep(i, 1, n)68 ????????????for (register int j = 0; j < G[i].size(); ++j)69 ????????????????if (sccno[i] != sccno[G[i][j]]) b[sccno[G[i][j]]] = 1;70 ????????rep(i, 1, sc) if (!b[i]) ans1++;71 ????????printf("%d\n", ans1);72 ????????maxx(ans, ans1);73 ????} else printf("1\n");74 ????printf("%d", ans);75 76 ????return 0;77 }