Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #1970387) | Cod sursa (job #796589) | Cod sursa (job #334262) | Cod sursa (job #1850252)
#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,k;
vector<int> v[MAXN],r;
vector< vector<int> > CTC;
stack<int> s;
int id[MAXN],lowlink[MAXN];
bool in_stack[MAXN];
void tarjan(int nod)
{
id[nod]=lowlink[nod]=k;
k++;
s.push(nod);
in_stack[nod]=1;
for(int i : v[nod])
{
if(id[i]==-1)
{
tarjan(i);
lowlink[nod]=min(lowlink[nod],lowlink[i]);
}
else if(in_stack[i])
lowlink[nod]=min(lowlink[nod],lowlink[i]);
}
if(id[nod]==lowlink[nod])
{
r.clear();
int t;
do{
r.push_back(t=s.top());
s.pop();
in_stack[t]=0;
}while(t!=nod);
CTC.push_back(r);
}
}
int main()
{
in>>n>>m;
for(int i=0;i<m;++i)
{
int x,y;
in>>x>>y;
v[x-1].push_back(y-1);
}
memset(id,-1,MAXN);
for(int i=0;i<n;++i)
if(id[i]==-1)
tarjan(i);
out<<CTC.size()<<'\n';
for(int i=0;i<CTC.size();++i)
{
for(int j=0;j<CTC[i].size();++j)
out<<CTC[i][j]+1<<' ';
out<<'\n';
}
return 0;
}