VIJOS-P1626 爱在心中
vijos 心中
2023-09-11 14:20:17 时间
VIJOS-P1626 爱在心中
JDOJ 1588
https://neooj.com/oldoj/problem.php?id=1588
TARJAN求强连通分量的模板题
AC代码
#include<cstdio> #include<algorithm> using namespace std; int n,m,ans,sum; int tot,to[10001],nxt[10001],head[1001]; int rudu[1001],chudu[1001]; int z[1001],inz[1001],v[1001],deep[1001],low[1001],belong[1001],top,cnt; int f[1001][1001]; void add(int x,int y) { to[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } void tarjan(int x) { z[++top]=x; v[x]=1; inz[x]=1; deep[x]=low[x]=++cnt; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(v[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); } else if(inz[y]==1) low[x]=min(low[x],deep[y]); } if(deep[x]==low[x]) { ans++; int t; do { t=z[top--]; inz[t]=0; f[ans][++f[ans][0]]=t; belong[t]=ans; }while(t!=x); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); rudu[b]++; } for(int i=1;i<=n;i++) if(v[i]==0) tarjan(i); for(int i=1;i<=ans;i++) if(f[i][0]!=1) sum++; printf("%d\n",sum); for(int i=1;i<=n;i++) for(int j=head[i];j;j=nxt[j]) if(belong[i]!=belong[to[j]]) chudu[belong[i]]++; sum=0; int pos; for(int i=1;i<=ans;i++) if(chudu[i]==0) sum++,pos=i; if(sum!=1 || f[pos][0]==1) printf("-1"); else { int a=f[pos][0]; f[pos][0]=0; sort(f[pos]+1,f[pos]+a+1); for(int i=1;i<=a;i++) printf("%d ",f[pos][i]); } return 0; }
相关文章
- 【25.00%】【vijos P1907】飞扬的小鸟
- 【19.00%】【vijos p1906】联合权值
- 【30.00%】【vijos 1909】寻找道路
- 【33.00%】【vijos P1002】过河
- 【37.00%】【vijos p1425】子串清除
- 【21.00%】【vijos P1018】智破连环阵
- Vijos P1002 过河 (NOIP提高组2005)
- vijos P1352 最大获利(最小割)
- vijos-1382 寻找主人
- vijos - P1543极值问题(斐波那契数列 + 公式推导 + python)
- Vijos P1881 闪烁的星星
- Vijos、洛谷——金明的预算方案(java实现)
- Vijos——小飞侠的游园方案(java实现)
- Vijos、洛谷——装箱问题(java实现)
- vijos 、洛谷 —— 珠心算测验(java实现)
- Vijos、洛谷——开心的金明(java实现)
- Vijos、洛谷——NASA的食物计划(java解法)
- Vijos、洛谷——采药(部分背包问题)(java实现)