ebzyl @ 2023-07-13 13:06:29
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int num;//当前已经dfs了num个点
int dfn[maxn];//dfn[i] 第i个点是第几个被dfs到的
int low[maxn];
vector<int> z[maxn];
void add_edge(int p1,int p2){
z[p1].push_back(p2);
}
bool jzy[maxn];
//low[i]代表
//从i点出发 沿着回边 树边 或者 能扩大环的横叉边 走
//能走到的所有点中 dfn最小的是多少
stack<int> s; //栈用来存储 被 dfs过 但还没有求出强连通分量的点
bool instack[maxn];//instack[i] 代表i点是否在栈里面
int cnt=0;//有几个强连通分量
queue<int> belong[maxn];//belong[i] 代表i点属于哪一个强连通分量
void dfs(int i)//当前搜索到了i点
{
num++;
dfn[i]=low[i]=num;
s.push(i);
instack[i]=true;
for (int k=0;k<z[i].size();k++)
{
int j = z[i][k];
if (!dfn[j])//树边
{
dfs(j);
low[i]=min(low[i],low[j]);
}
else//非树边
{
//这是一条回边 或者 能扩大环的横叉边
if (instack[j]) low[i]=min(low[i],dfn[j]);
//if (instack[j]) low[i]=min(low[i],low[j]);
}
}
if (dfn[i] == low[i])
{
cnt++;//多了一个强连通分量
while (s.top() != i)
{
belong[s.top()].push(cnt);
instack[s.top()] = false;
s.pop();
}
s.pop();
instack[i]=false;
belong[i].push(cnt);
}
}
int n,m;
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int p1,p2;
cin >> p1 >> p2;
add_edge(p1,p2);
}
for (int i=1;i<=n;i++)
if (!dfn[i]) dfs(i);
cout<<cnt<<'\n';
for(int i=1;i<=n;i++){
while(belong[i].size()!=0){
if(jzy[belong[i].front()]==false){
jzy[belong[i].front()]==true;
cout<<belong[i].front()<<' ';
}
belong[i].pop();
}
cout<<'\n';
}
}
输出有问题,求调