Pagini recente » Cod sursa (job #2445893) | Cod sursa (job #1303447) | Cod sursa (job #1630867) | Cod sursa (job #953057) | Cod sursa (job #829929)
Cod sursa(job #829929)
#include <stdio.h>
#include <string.h>
#include <vector>
#define N 100005
using namespace std;
vector <int> v[N];
vector <int> u[N];
vector <int> r[N];
int t[N],C[N],sol[N];
int n,m,i,j,componente,S,k;
void citire()
{
int i,x,y;
scanf ("%d%d", &n,&m);
for (i=1;i<=m;i++)
{
scanf ("%d%d", &x,&y);
v[x].push_back(y);
u[y].push_back(x);
}
}
void dfs(int nod, vector <int> v[N], int value)
{
int i,L=v[nod].size();
t[nod]=1;
for (i=0;i<L;i++)
if (t[v[nod][i]]==0)
dfs(v[nod][i], v, value);
if (value==1)
C[++S]=nod;
else
sol[++k]=nod;
}
int main()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
citire();
for (i=1;i<=n;i++)
if (t[i]==0)
dfs(i,v, 1);
memset (t, 0, sizeof(t));
for (i=S;i>=1;i--)
if (t[C[i]]==0)
{
componente++; k=0;
dfs(C[i], u, 2);
for (j=1;j<=k;j++)
r[componente].push_back(sol[j]);
}
printf ("%d\n", componente);
for (i=1;i<=componente;i++)
{
k=r[i].size();
for (j=0;j<k;j++)
printf ("%d ", r[i][j]);
printf ("\n");
}
return 0;
}