Peking University Online Judge 3180 The Cow Prom
・sccを貼っただけ
・全部の関数を使う必要があるのか
・そもそも本当にsccの問題なのか
などの理由で消化不良、本当に実力はついているのか
#include<cstdio> #include<vector> #include<algorithm> using namespace std; static const int MAX_N = 10000; int N, M; vector<int> G[MAX_N]; vector<int> rG[MAX_N]; vector<int> vs; bool used[MAX_N]; int cmp[MAX_N]; int num[MAX_N]; void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i]]) dfs(G[v][i]); } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(int i = 0; i < rG[v].size(); i++){ if(!used[rG[v][i]]) rdfs(rG[v][i], k); } } int scc(){ fill(used, used + N, false); vs.clear(); for(int i = 0; i < N; i++){ if(!used[i]) dfs(i); } fill(used, used + N, false); int k = 0; for(int i = vs.size() - 1; i >= 0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } return k; } int main(){ scanf("%d %d", &N, &M); for(int i = 0; i < M; i++){ int u, v; scanf("%d %d", &u, &v); u--; v--; add_edge(u, v); } int n = scc(); for(int i = 0; i < N; i++){ num[cmp[i]]++; } int res = 0; for(int i = 0; i < n; i++){ if(num[i] >= 2) res++; } printf("%d\n", res); return 0; }