Pagini recente » Cod sursa (job #2794534) | Cod sursa (job #742899) | Cod sursa (job #1943450) | Cod sursa (job #240971) | Cod sursa (job #935632)
Cod sursa(job #935632)
#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, bool add_to_sol, vector<int> vec[maxn]){
sel[a] = 1;
if( add_to_sol ) {
sol[nr_ctc].push_back(a);
}
for( int i = 0; i < vec[a].size(); ++i)
if( sel[vec[a][i]] == 0)
df(vec[a][i], add_to_sol, vec);
if( add_to_sol == false)
parc.push(a);
}
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, 0, vec);
}
memset(sel, 0, sizeof(sel));
while( ! parc.empty() ){
int val = parc.top();
parc.pop();
if( sel[val] == 0) {
df(val, 1, vect);
nr_ctc++;
}
}
afisare_sol();
return 0;
}