Pagini recente » Cod sursa (job #2146945) | Cod sursa (job #1379454) | Cod sursa (job #2345814) | Cod sursa (job #2719948) | Cod sursa (job #935643)
Cod sursa(job #935643)
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
#define maxn 100001
int sel[maxn];
int nr_ctc, n;
stack <int> parc;
vector <int> sol[maxn];
vector <int> vec[maxn];
vector <int> vect[maxn];
void afisare_sol(){
cout<<nr_ctc<<endl;
for( int i = 0; i < nr_ctc; ++i) {
for( int j = 0; j < sol[i].size(); ++j) {
cout<<sol[i][j]<<" ";
}
cout<<endl;
}
}
void df(int a){
sel[a] = 1;
for( int i = 0; i < vec[a].size(); ++i)
if( sel[vec[a][i]] == 0)
df(vec[a][i]);
parc.push(a);
}
void df2(int a){
sel[a] = 1;
sol[nr_ctc].push_back(a);
for( int i = 0; i < vect[a].size(); ++i)
if( sel[vect[a][i]] == 0)
df2(vect[a][i]);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int mm;
scanf("%d %d", &n, &mm);
for( int i = 1; i <= mm; ++i) {
int a, b;
scanf("%d %d", &a, &b);
vec[a].push_back(b);
vect[b].push_back(a);
}
for( int i = 1; i <= n; ++i)
if( sel[i] == 0) {
df(i);
}
memset(sel, 0, sizeof(sel));
while( ! parc.empty() ){
int val = parc.top();
parc.pop();
if( sel[val] == 0) {
df2(val);
nr_ctc++;
}
}
afisare_sol();
return 0;
}