Pagini recente » Cod sursa (job #1245560) | Cod sursa (job #499050) | Cod sursa (job #1335274) | Cod sursa (job #1357027) | Cod sursa (job #948403)
Cod sursa(job #948403)
#include<stdio.h>
#include<iostream>
#include<fstream>
#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 <vector <int> > sol;
vector <int> vec[maxn];
vector <int> vect[maxn];
void afisare_sol(){
ofstream out("ctc.out");
out << sol.size() << "\n";
for (size_t i = 0; i < sol.size(); ++ i) {
for (size_t j = 0; j < sol[i].size(); ++ j)
out << sol[i][j] << " ";
out << "\n";
}
out.close();
}
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[sol.size() - 1].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;
cin>>n>>mm;
for( int i = 1; i <= mm; ++i) {
int a, b;
cin>>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) {
vector<int> temp;
sol.push_back(temp);
df2(val);
}
}
afisare_sol();
return 0;
}