Pagini recente » Cod sursa (job #950661) | Cod sursa (job #2954957) | Cod sursa (job #1402112) | Cod sursa (job #1983715) | Cod sursa (job #1155340)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define nmax 100005
using namespace std;
int n, m, a, b, comps = 0;
bool seen[nmax];
vector <int> v[nmax], vt[nmax], comp[nmax];
stack <int> S;
void dfs(int x) {
seen[x] = true;
for(int i=0; i<int(v[x].size()); i++) if(!seen[v[x][i]]) dfs(v[x][i]);
S.push(x);
}
void secondDfs(int x) {
seen[x] = true;
comp[comps].push_back(x);
for(int i=0; i<int(vt[x].size()); i++) if(!seen[vt[x][i]]) secondDfs(vt[x][i]);
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(int i=1; i<=m; i++) {
f>>a>>b;
v[a].push_back(b);
vt[b].push_back(a);
}
for(int i=1; i<=n; i++) if(!seen[i]) dfs(i);
memset(seen, 0, nmax*sizeof(bool));
while(!S.empty()) {
int x = S.top();
S.pop();
if(!seen[x]) {
secondDfs(x);
comps++;
}
}
g<<comps<<"\n";
for(int i=0; i<comps; i++) {
for(int j=0; j<int(comp[i].size()); j++) g<<comp[i][j]<<" ";
g<<"\n";
}
return 0;
}