Pagini recente » Cod sursa (job #3162608) | Cod sursa (job #3207450) | Cod sursa (job #1935632) | Cod sursa (job #383867) | Cod sursa (job #2839359)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax=1e5+5;
int n,m,indecs=1;
vector<int> vecini[nmax];
int idx[nmax],lowlink[nmax];
stack<int> S;
bool in_stack[nmax];
vector<vector<int> > C;
void tarjan(int nod)
{
idx[nod]=indecs;
lowlink[nod]=indecs;
indecs++;
S.push(nod);
in_stack[nod]=true;
for(auto pi: vecini[nod])
{
if(idx[pi]==0)
{
tarjan(pi);
lowlink[nod]=min(lowlink[nod],lowlink[pi]);
}
else if(in_stack[pi])
{
lowlink[nod]=min(lowlink[nod],lowlink[pi]);
}
}
if(lowlink[nod]==idx[nod])
{
vector<int> comp;
int i;
do{
i=S.top();
comp.push_back(i);
in_stack[i]=0;
S.pop();
}while(i!=nod);
C.push_back(comp);
}
}
int main()
{
fin>>n>>m;
for(int i=1; i<=m; i++)
{
int a,b;
fin>>a>>b;
vecini[a].push_back(b);
}
for(int i=1; i<=n; i++)
{
if(idx[i]==0)
{
tarjan(i);
}
}
fout<<C.size()<<"\n";
for(int i=0; i<C.size(); i++)
{
for(auto el : C[i]) fout<<el<<" ";
fout<<"\n";
}
return 0;
}