Pagini recente » Cod sursa (job #507019) | Cod sursa (job #79253) | Cod sursa (job #73237) | Cod sursa (job #2938528) | Cod sursa (job #1348200)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
vector<int> CC[Nmax];
vector<int> Gi[Nmax];
vector<int> G[Nmax];
stack<int> S;
int vizi[Nmax];
int viz[Nmax];
int n, m;
int nrc;
void citire()
{
int x, y;
scanf("%d %d\n", &n, &m);
for(int i=1; i<=m; ++i)
{
scanf("%d %d\n", &x, &y);
G[x].push_back(y);
Gi[y].push_back(x);
}
}
void parcurgere(int vf)
{
viz[vf] = 1;
for(vector<int>::iterator it = G[vf].begin(); it != G[vf].end(); ++it)
{
if(!viz[*it])
parcurgere(*it);
}
S.push(vf);
}
void dfs(int k)
{
vizi[k] = 1;
for(vector<int>::iterator it = Gi[k].begin(); it != Gi[k].end(); ++it)
{
if(!vizi[*it])
{
CC[nrc].push_back(*it);
dfs(*it);
}
}
}
void afisare()
{
/*
while(!S.empty())
{
printf("%d ", S.top());
S.pop();
}
*/
printf("%d\n", nrc);
for(int i=0; i<nrc; ++i)
{
for(vector<int>::iterator it = CC[i].begin(); it!=CC[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
}
void sol1()
{
for(int i = 1; i<=n; ++i)
if(!viz[i])
parcurgere(i);
}
void sol2()
{
while(!S.empty())
{
int aux = S.top();
S.pop();
if(!vizi[aux])
{
CC[nrc].push_back(aux);
dfs(aux);
nrc++;
}
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
sol1();
sol2();
afisare();
return 0;
}