Pagini recente » Cod sursa (job #1254229) | Cod sursa (job #496938) | Cod sursa (job #60528) | Cod sursa (job #1755267) | Cod sursa (job #1832181)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<bool> onStack;
vector<int> dis,low;
vector<int> G[100001],comp[100001];
int n,m,x,y,ind=1,cnt,topStack;
stack<int> S;
void strongConnect(int);
int main()
{
fin>>n>>m;
onStack.resize(n+1,false);
dis.resize(n+1,-1);
low.resize(n+1,-1);
for(int i=1;i<=m;i+=1)
{
fin>>x>>y;
G[x].push_back(y);
}
for(int i=1;i<=n;i+=1)if(dis[i]==-1)
strongConnect(i);
fout<<cnt<<'\n';
for(int i=1;i<=cnt;i+=1)
{
for(auto j:comp[i])fout<<j<<' ';
fout<<'\n';
}
return 0;
}
void strongConnect(int x)
{
dis[x]=ind;
low[x]=ind++;
onStack[x]=true;
S.push(x);
for(auto i:G[x])
{
if(dis[i]==-1)
{
strongConnect(i);
low[x]=min(low[x],low[i]);
}
else if(onStack[i])
{
low[x]=min(low[x],dis[i]);
}
}
if(dis[x]==low[x])
{
cnt+=1;
do
{
topStack=S.top();
onStack[topStack]=false;
comp[cnt].push_back(topStack);
S.pop();
}
while(topStack!=x);
}
}