Codeforces Round #286 div.2 D 505D. Mr. Kitayuta's Technology【强连通分量,弱联通分量】
题目链接:http://codeforces.com/contest/505/problem/D
题目大意:
分析:
#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; #define N 100010 vector<int> g[N]; vector<int> rg[N]; vector<int> vs; bool used[N]; int cmp[N]; int n,m; void add_edge(int from,int to) { g[from].push_back(to); rg[to].push_back(from); } void dfs(int v) { used[v]=1; 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]=1; cmp[v]=k; for(int i=0;i<rg[v].size();i++) if(!used[rg[v][i]]) rdfs(rg[v][i],k); } int scc() { memset(used,0,sizeof(used)); vs.clear(); for(int v=0;v<n;v++) if(!used[v]) dfs(v); memset(used,0,sizeof(used)); int k=0; for(int i=vs.size()-1;i>=0;i--) if(!used[vs[i]]) rdfs(vs[i],k++); return k; } int cmpsize[N]; bool dfs2(int v) { used[v]=1; bool ans=(cmpsize[cmp[v]]==1); for(int i=0;i<g[v].size();i++) { if(!used[g[v][i]]) ans &= (dfs2(g[v][i])==1); } for(int i=0;i<rg[v].size();i++) { if(!used[rg[v][i]]) ans &= (dfs2(rg[v][i])==1); } return ans; } int main() { while(~scanf("%d%d",&n,&m)) { memset(cmpsize,0,sizeof(cmpsize)); for(int i=0;i<n;i++) rg[i].clear(),g[i].clear(); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); add_edge(u-1,v-1); } scc(); memset(used,0,sizeof(used)); for(int i=0;i<n;i++) cmpsize[cmp[i]]++; int ans=n; for(int i=0;i<n;i++) { if(!used[i]) ans -= dfs2(i); } cout<<ans<<endl; } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。