Tarjan算法——有向图环问题的killer

P2863 [USACO06JAN]牛的舞会The Cow Prom

洛谷模板题

题目

问节点大于1的强联通分量个数

题解

染色的代码稍微修改即可

#include<bits/stdc++.h> #define maxl 400010 using namespace std; int n,k,ff,top,cnt,cnt2,id,num,m,m1,m2; int a[maxl],b[maxl],s[maxl]; int ehead[maxl],ehead2[maxl]; struct ed { int to,w,nxt; }e[maxl],e2[maxl]; int f[maxl],dfn[maxl],low[maxl]; bool in[maxl]; bool ansflag; //链式前向星 inline void add(int u,int v) { e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt; } inline void tarjan(int u) { int v;s[++top]=u;in[u]=true; dfn[u]=low[u]=++num; for(int i=ehead[u];i;i=e[i].nxt) { v=e[i].to; if(!dfn[v]) { tarjan(v); if(low[v]<low[u]) low[u]=low[v]; } else if(in[v] && dfn[v]<low[u]) low[u]=dfn[v]; } if(dfn[u]==low[u]) { ff++; do { v=s[top];s[top]=0;top--; f[ff]++; in[v]=false; }while(v!=u); } } int main() { cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d",&m1,&m2); add(m1,m2); } for(int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } int ans=0; for(int i=1;i<=ff;i++){ if(f[i]>1) ans++; } cout<<ans<<endl; }

P2341 [HAOI2006]受欢迎的牛|【模板】强连通分量

缩点模板题

题目

求有向图中所有点都能到达的点

题解

我们考虑加入图中没有环的情况，那么出度为0的点就一定就是这个点，加入有两个及以上出度为0的点，则这样的点不存在，因为这几个出度为0的点必不能互相到达 然后再考虑有环的情况，有环的情况比较复杂，但考虑到环内所有点的地位相同，作用相同，所以我们将每一个环都缩成一个点，这样就能按照上述情况讨论了（虽说是模板题，其实还是挺有难度的） 所谓的缩点实质在我看来就是先把一个强联通分量中的所有点染上同样的颜色，然后遍历每一条边的时候只要边的起点与终点点的颜色相同，就跳过这条边，如果不同，就对两个点的联通分量的编号进行操作（而不是直接对两个点进行操作），这样就达成了缩点的目的

#include<bits/stdc++.h> #define maxl 400010 using namespace std; int n,k,ff,top,cnt,cnt2,id,num,m,m1,m2; int a[maxl],b[maxl],s[maxl],du[maxl]; int head[maxl],head2[maxl]; struct ed { int to,w,nxt; }e[maxl],e2[maxl]; int f[maxl],dfn[maxl],low[maxl]; bool in[maxl]; bool ansflag; //链式前向星 inline void add(int u,int v) { e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt; } inline void tarjan(int u) { int v;s[++top]=u;in[u]=true; dfn[u]=low[u]=++num; for(int i=head[u];i;i=e[i].nxt) { v=e[i].to; if(!dfn[v]) { tarjan(v); if(low[v]<low[u]) low[u]=low[v]; } else if(in[v] && dfn[v]<low[u]) low[u]=dfn[v]; } if(dfn[u]==low[u]) { ff++; do { v=s[top];s[top]=0;top--; f[v]=ff; in[v]=false; }while(v!=u); } } int main() { cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d",&m1,&m2); add(m1,m2); } for(int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(int i=1;i<=n;i++){ for(int j=head[i];j;j=e[j].nxt){ m=e[j].to; if(f[i]!=f[m]){ du[f[i]]++; } } } int ans=0,t=0; for(int i=1;i<=ff;i++){ if(du[i]==0){ ans++; if(ans>1) continue; for(int j=1;j<=n;j++){ if(f[j]==i) t++; } } } if(ans!=1) cout<<'0'<<endl; else cout<<t<<endl; }

P1262 间谍网络

缩点应用题

题目

给出几个节点的权值，询问是否可以通过这几个点遍历到所有的点，如果可以问所需点权值的最小值，如果不可以输出不能遍历到的点的序号最小值

题解

和上一题差不多吧，缩点后无环的有向图，入度为0的点是不需要选取的点，只要入度为0的点取不了答案就是NO，都取得了的话，就把所有点的权值相加就行（注意，缩点后点的权值为环中权值最小点的权值）

#include<bits/stdc++.h> #define maxl 400010 using namespace std; const int M=40000; int n,k,ff,top,cnt,cnt2,id,num,m,m1,m2; int a[maxl],b[maxl],s[maxl],v1[maxl],f1[maxl],du[maxl]; int head[maxl],head2[maxl]; struct ed { int to,w,nxt; }e[maxl],e2[maxl]; int f[maxl],dfn[maxl],low[maxl]; bool in[maxl]; bool ansflag; //链式前向星 inline void add(int u,int v) { e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt; } inline void tarjan(int u) { int v;s[++top]=u;in[u]=true; dfn[u]=low[u]=++num; for(int i=head[u];i;i=e[i].nxt) { v=e[i].to; if(!dfn[v]) { tarjan(v); if(low[v]<low[u]) low[u]=low[v]; } else if(in[v] && dfn[v]<low[u]) low[u]=dfn[v]; } if(dfn[u]==low[u]) { ff++; f1[ff]=M; do { v=s[top];s[top]=0;top--; f[v]=ff; if(v1[v]) f1[ff]=min(f1[ff],v1[v]); in[v]=false; }while(v!=u); } } int main() { //freopen("1.txt","r",stdin); cin>>n>>k; for(int i=1;i<=k;i++){ scanf("%d%d",&m1,&m2); v1[m1]=m2; } cin>>m; for(int i=1;i<=m;i++){ scanf("%d%d",&m1,&m2); add(m1,m2); } for(int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(int i=1;i<=n;i++){ for(int j=head[i];j;j=e[j].nxt){ m=e[j].to; if(f[i]!=f[m]) du[f[m]]++; } } int ans=0; for(int i=1;i<=n;i++){ if(du[f[i]]==0){ if(f1[f[i]]==M){ cout<<"NO\n"<<i<<endl; return 0; } } } for(int i=1;i<=ff;i++){ if(du[i]==0) ans+=f1[i]; } cout<<"YES\n"<<ans<<endl; //fclose(stdin); }