社区讨论
求助,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 条回复,欢迎继续交流。
正在加载回复...