Pagini recente » Cod sursa (job #2113236) | Cod sursa (job #849963) | Cod sursa (job #2483371) | Cod sursa (job #2810825) | Cod sursa (job #1455852)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define NMAX 100007
using namespace std;
vector < int > v[NMAX], V[NMAX], Sol[NMAX];
bool Viz[NMAX];
int Ans[NMAX];
int n, m, NrSol;
void dfs(int Nod){
Viz[Nod] = 1;
for(vector < int >::iterator it = v[Nod].begin(); it != v[Nod].end(); ++it)
if(Viz[*it] == 0)
dfs(*it);
Ans[++Ans[0]] = Nod;
}
void dfs2(int Nod){
Viz[Nod] = 1;
Sol[NrSol].push_back(Nod);
for(vector < int >::iterator it = V[Nod].begin(); it != V[Nod].end(); ++it)
if(Viz[*it] == 0)
dfs2(*it);
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i){
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
V[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(Viz[i] == 0)
dfs(i);
memset(Viz, 0, sizeof(Viz));
for(int i = n; i >= 1; --i)
if(Viz[Ans[i]] == 0){
++NrSol;
dfs2(Ans[i]);
}
printf("%d\n", NrSol);
for(int i = 1; i <= NrSol; ++i){
printf("%d ", Sol[i].size());
sort(Sol[i].begin(), Sol[i].end());
for(vector < int >::iterator it = Sol[i].begin(); it != Sol[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}