社区讨论
初学tarjan板子题求助
P2863[USACO06JAN] The Cow Prom S参与者 13已保存回复 35
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 35 条
- 当前快照
- 1 份
- 快照标识符
- @mi7cgz5a
- 此快照首次捕获于
- 2025/11/20 19:25 4 个月前
- 此快照最后确认于
- 2025/11/20 23:42 4 个月前
CPP
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N=10010;
int n,m,num,sum,color[N]; // color表示每个强联通分量的个数
int dfn[N],low[N],ans;
bool vis[N];
vector<int> v[N];
stack<int> s;
void tarjan(int x) // 当前点
{
dfn[x]=low[x]=++num;
s.push(x);
vis[x]=true;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i];
if(!dfn[y]) // 如果这个点没访问过
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else low[x]=min(low[x],dfn[y]); // 访问过
}
if(low[x]==dfn[x])
{
sum++;
while(s.top()!=x)
{
vis[s.top()]=false;
s.pop();
color[sum]++;
}
}
}
int main()
{
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
v[a].push_back(b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=sum;i++) if(color[i]>1) ans++;
cout<<ans;
return 0;
}
八十分 不知道哪里挂了
回复
共 35 条回复,欢迎继续交流。
正在加载回复...