Pagini recente » Cod sursa (job #2227432) | Cod sursa (job #330420) | Cod sursa (job #1229898) | Cod sursa (job #993478) | Cod sursa (job #2120949)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define min(a, b) a<b?a:b
#define N 100005
using namespace std;
vector <int> graf[N], sol[N];
stack <int> s;
vector <int> :: iterator it;
int viz[N], n, m, nr, index[N], lowlink[N], ind=1;
void citire()
{
scanf("%d %d\n", &n, &m);
for(int i=0;i<m;i++)
{
int x, y;
scanf("%d %d\n", &x, &y);
graf[x].push_back(y);
}
}
void afisare()
{
printf("%d\n", nr);
for(int i=1;i<=nr;i++)
{
for(int j=0;j<sol[i].size();j++)
printf("%d ", sol[i][j]);
printf("\n");
}
}
void dfs(int x)
{
index[x]=lowlink[x]=++ind;
s.push(x);
viz[x]=1;
for(int i=0;i<graf[x].size();i++)
{
int nod=graf[x][i];
if(!index[nod])
{
dfs(nod);
lowlink[x]=min(lowlink[x], lowlink[nod]);
}
else
if(viz[nod])
lowlink[x]=min(lowlink[x], index[nod]);
}
if(lowlink[x]==index[x])
{
nr++;
int y;
do {
y = s.top();
sol[nr].push_back(y);
s.pop();
viz[y] = 0;
} while(y != x);
}
}
void tarjan()
{
for(int i=1;i<=n;i++)
if(!index[i])
dfs(i);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
tarjan();
afisare();
return 0;
}