Pagini recente » Cod sursa (job #2846577) | Cod sursa (job #887448) | Cod sursa (job #3180367) | Cod sursa (job #2529885) | Cod sursa (job #2872540)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N=1e5;
struct graf
{
vector<int> v;
}la[N+5];
stack<int> stk;
int id[N+5],low[N+5];
bool onStk[N+5];
int nrCTC,nrid;
vector<vector<int> >ctc;
void dfs(int nod)
{
low[nod]=id[nod]=++nrid;
stk.push(nod);
onStk[nod]=1;
for(int i=0;i<la[nod].v.size();i++)
{
int to=la[nod].v[i];
if(id[to] == -1) dfs(to);
if(onStk[to]) low[nod]=min(low[to],low[nod]);
}
if(low[nod] == id[nod])
{
vector<int> aux;
while(stk.top()!=nod)
{
aux.push_back(stk.top());
onStk[stk.top()]=0;
stk.pop();
}
aux.push_back(stk.top());
onStk[stk.top()]=0;
stk.pop();
ctc.push_back(aux);
nrCTC++;
}
}
void Tarjan(int n)
{
for(int i=1;i<=n;i++) id[i]=-1;
for(int i=1;i<=n;i++)
if(id[i] == -1)
{
dfs(i);
}
}
int main()
{
int n,m; cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y; cin>>x>>y;
la[x].v.push_back(y);
}
Tarjan(n);
out<<nrCTC<<'\n';
for(int i=0;i<ctc.size();i++)
{
for(int j=0;j<ctc[i].size();j++)
out<<ctc[i][j]<<' ';
out<<'\n';
}
return 0;
}