1 条题解
-
0
问题描述:
给定一个有向图,将其每个强连通分量(SCC)缩为一个节点后得到一个DAG。若该DAG中存在且仅存在一个入度为0的节点(源点),则输出该源点对应的SCC的大小;若不存在或存在多个源点,则输出0。
算法思路:
- 使用Tarjan算法求解图中所有强连通分量(SCC),记录每个节点所属的SCC编号及每个SCC的大小。
- 将原图缩点为DAG,计算每个SCC在DAG中的出度(即该SCC中节点指向其他SCC节点的边的数量)。
- 检查DAG中出度为0的SCC数量:若超过1个,输出0;若恰好1个,输出该SCC的大小;否则(0个)也输出0。
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; vector<int>G[N]; int tsp,cnt,low[N],dfn[N],scc[N],num[N]; stack<int>stk;bool instk[N]; void tarjan(int x) { dfn[x]=low[x]=++tsp; stk.push(x);instk[x]=1; for(int y:G[x]) { if(dfn[y]==0) { tarjan(y); low[x]=min(low[x], low[y]); } else if(instk[y]) low[x]=min(low[x], dfn[y]); } if(low[x]==dfn[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top();stk.pop();instk[z]=0; scc[z]=cnt; num[cnt]++; } } } int main() { int n,m;scanf("%d%d",&n,&m); memset(G,0,sizeof(G)); for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y); tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(instk,0,sizeof(instk));memset(scc,0,sizeof(scc)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i); vector<int>cd(n+1); for(int i=1;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j])cd[scc[i]]++; int p=0; for(int i=1;i<=cnt;i++)if(cd[i]==0) { if(p==0)p=i; else { printf("0\n"); return 0; } } printf("%d\n",num[p]); return 0; }
- 1
信息
- ID
- 2704
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 82
- 已通过
- 35
- 上传者