Pagini recente » Cod sursa (job #814306) | Cod sursa (job #709918) | Cod sursa (job #2826980) | Cod sursa (job #2576751) | Cod sursa (job #1170870)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
// Q = o coada in care adaug mereu la final; Q[0] = nr de elmente din coada.
vector<int> adj[100000], inv[100000], ctc[100000];
int n, m, Q[100001], viz[100000], comp;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs_direct(int start) {
viz[start] = 1;
for(vector<int>::iterator it = adj[start].begin(); it != adj[start].end(); ++it) {
if(viz[*it] == 0) {
dfs_direct(*it);
}
}
Q[++Q[0]] = start;
}
void dfs_invers(int start) {
viz[start] = 1;
ctc[comp-1].push_back(start);
for(vector<int>::iterator it = inv[start].begin(); it != inv[start].end(); ++it) {
if(viz[*it] == 0) {
dfs_invers(*it);
}
}
}
int main() {
int i, u, v;
fin >> n >> m;
for(i = 0; i < m; i++) {
fin >> u >> v;
u--, v--;
adj[u].push_back(v);
inv[v].push_back(u);
}
for(i = 0; i < n; i++) {
if(viz[i] == 0) {
dfs_direct(i);
}
}
memset(viz, 0, n*sizeof(int));
for(i = Q[0]; i > 0; i--) {
if(viz[Q[i]] == 0) {
comp++;
dfs_invers(Q[i]);
}
}
fout << comp << "\n";
for(i = 0; i < comp; i++) {
for(vector<int>::iterator it = ctc[i].begin(); it != ctc[i].end(); ++it) {
fout << *it + 1 << " ";
}
fout << "\n";
}
return 0;
}