1 条题解

  • 0
    @ 2025-10-8 17:02:35

    问题描述:

    给定一个有向图,将其每个强连通分量(SCC)缩为一个节点后得到一个DAG。若该DAG中存在且仅存在一个入度为0的节点(源点),则输出该源点对应的SCC的大小;若不存在或存在多个源点,则输出0。

    算法思路:

    1. 使用Tarjan算法求解图中所有强连通分量(SCC),记录每个节点所属的SCC编号及每个SCC的大小。
    2. 将原图缩点为DAG,计算每个SCC在DAG中的出度(即该SCC中节点指向其他SCC节点的边的数量)。
    3. 检查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

    D15_2【强连通SCC】[USACO03FALL / HAOI2006] 受欢迎的牛 G

    信息

    ID
    2704
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    82
    已通过
    35
    上传者