社区讨论

求助,Kosaraju算法

P2835刻录光盘参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m4p2lpym
此快照首次捕获于
2024/12/15 11:52
去年
此快照最后确认于
2024/12/15 15:57
去年
查看原帖
CPP
#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;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...