Pagini recente » Cod sursa (job #2693166) | Cod sursa (job #2909991) | Cod sursa (job #1681645) | Cod sursa (job #3293791) | Cod sursa (job #1241369)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
#define size 100001
int n, m, sw[size], solind;
vector<int> graf[size], tgraf[size], sol[size], stack;
void df1(int nod){
stack.push_back(nod);
sw[nod] = 1;
for (vector<int> :: iterator it = graf[nod].begin(); it < graf[nod].end(); it++) {
if (sw[*it] == 0) {
df1(*it);
}
}
}
void df2(int nod) {
sol[solind].push_back(nod);
sw[nod] = 1;
for( vector<int> :: iterator it = tgraf[nod].begin(); it < tgraf[nod].end(); it ++) {
if ( sw[*it] == 0) {
df2(*it);
}
}
}
void solve() {
for (int i = 1; i <=n ; i++) {
if ( sw[i] == 0) {
df1(i);
}
}
memset(sw, 0, sizeof(sw));
solind = 0;
for (int i = n-1; i>=0; i--) {
int nod = stack[i];
if (sw[nod] == 0) {
df2(nod);
solind ++;
}
}
}
void afisare() {
ofstream g("ctc.out");
g << solind << '\n';
for (int i = 0 ; i < solind ; i ++) {
for (vector<int> :: iterator it = sol[i].begin(); it < sol[i].end(); it ++) {
g << *it <<' ' ;
}
g << '\n';
}
g.close();
}
void citire() {
ifstream f("ctc.in");
f >> n >> m;
for (int i = 1; i <=m; i++) {
int x, y;
f >> x >> y ;
graf[x].push_back(y);
tgraf[y].push_back(x);
}
f.close();
}
int main()
{
citire();
solve();
afisare();
return 0;
}