Pagini recente » Cod sursa (job #2634040) | Cod sursa (job #1545028) | Cod sursa (job #2083604) | Cod sursa (job #1174501) | Cod sursa (job #288849)
Cod sursa(job #288849)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int N = 100005;
vector<int> a[N];
vector<int> c[N];
bool ins[N];
stack<int> stiva;
int n,ind[N],sub[N],indice,nrc;
inline int minim(int x,int y)
{
return x < y ? x : y ;
}
void citire()
{
int m,x,y;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
}
}
void dfs(int x)
{
ind[x] = ++indice;
stiva.push(x);
ins[x] = true;
sub[x] = indice;
int nr = a[x].size(),y;
for(int i=0 ; i<nr ; ++i)
{
y=a[x][i];
if(ind[y] == 0 || ins[y])
{
if(ind[y] == 0)
dfs(y);
sub[x] = minim(sub[x],sub[y]);
}
}
if(sub[x] == ind[x])
{
++nrc;
do
{
y=stiva.top();
stiva.pop();
c[nrc].push_back(y);
ins[y] = false;
}
while(y != x);
}
}
void componente()
{
int nr;
for(int i=1 ; i<=n ; ++i)
if(ind[i] == 0)
dfs(i);
printf("%d\n",nrc);
for(int i=1 ; i<=nrc ; ++i)
{
nr = c[i].size();
for(int j=0 ; j<nr ; ++j)
printf("%d ",c[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
componente();
return 0;
}