Pagini recente » Cod sursa (job #3277933) | Cod sursa (job #404929) | Cod sursa (job #3249325) | Cod sursa (job #3256305) | Cod sursa (job #492267)
Cod sursa(job #492267)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "ctc.in";
const char oname[] = "ctc.out";
const int MAX_N = 100005;
vector <int> Go[MAX_N], Gi[MAX_N], where[MAX_N], used, discovered;
void DFP(int n, vector <int> *G) {
vector <int>::iterator it;
used[n] = true;
for (it = G[n].begin(); it != G[n].end(); ++ it) if (!used[*it])
DFP(*it, G);
discovered.push_back(n);
}
void DFM(int n, vector <int>* G, int which) {
vector <int>::iterator it;
used[n] = true;
where[which].push_back(n);
for (it = G[n].begin(); it != G[n].end(); ++ it) if (!used[*it])
DFM(*it, G, which);
}
int main(void) {
int nodes, edges, x, y;
ifstream in(iname);
in >> nodes >> edges;
while (edges --) {
in >> x >> y;
Go[x - 1].push_back(y - 1);
Gi[y - 1].push_back(x - 1);
}
in.close();
used.resize(nodes);
used.assign(used.size(), false);
for (int i = 0; i < (int) used.size(); ++ i) if (!used[i])
DFP(i, Go);
used.assign(used.size(), false);
int count = 0;
for (; discovered.size(); discovered.pop_back()) {
if (!used[discovered.back()])
DFM(discovered.back(), Gi, count ++);
}
ofstream out(oname);
out << count << '\n';
for (int i = 0; i < (int) count; ++ i) {
for (int j = 0; j < (int) where[i].size(); ++ j)
out << (where[i][j] + 1) << " ";
out << '\n';
}
out.close();
return 0;
}