求助,Kosaraju算法
  • 板块P2835 刻录光盘
  • 楼主sjm2022
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/15 11:52
  • 上次更新2024/12/15 15:57:52
查看原帖
求助,Kosaraju算法
843406
sjm2022楼主2024/12/15 11:52
#include <bits/stdc++.h>
using namespace std;
bool a[100][100];   //图存储
int shu[100]={0};   //检测
queue <int> q;     //dfs顺序
queue <int> r;     //dfs出栈顺序
//Kosaraju
void dfs(int ren,int p)
{
    q.push(p);
    shu[p]=-1;      //标记
    for(int i=1;i<=ren;i++)
    {
        if(i==p||!a[p][i])    //未连接
        {
            continue;
        }
        dfs(ren,p);
    }
    r.push(q.front());
    shu[q.front()]=-1;
    q.pop();
}
int bianli(int ren)
{
    int answer=1;
    do
    {
        int temp=r.front();
        r.pop();
        if(a[temp][r.front()])   //判断连通
        {
            answer++;      //不连通就加一个光盘
        }
    }
    while(!r.empty());
    return answer;
}
int main()
{
    //freopen("cdrom.in","r",stdin);
    //freopen("cdrom.out","w",stdout);

    int ren=0;    //人数
    cin>>ren;

    for(int i=1;i<=ren;i++)
    {
        shu[i]=i;     //初始化
        int in=0;
        cin>>in;
        while(in!=0)
        {
            a[i][in]=true;    //确定路径
            cin>>in;
        }
    }

    for(int i=1;i<=ren;i++)
    {
        if(shu[i]==i)
        {
            dfs(ren,i);     //第一遍dfs
        }
    }

    cout<<bianli(ren)<<endl;    //第二遍dfs
    return 0;
}

2024/12/15 11:52
加载中...