Pagini recente » Cod sursa (job #2473744) | Cod sursa (job #2316963) | Cod sursa (job #2954087) | Cod sursa (job #2014184) | Cod sursa (job #760744)
Cod sursa(job #760744)
#include<stdio.h>
#include<vector>
#include<list>
using namespace std;
void dfs(int src, vector<bool> &viz, vector<list<int> > &G, list<int> &q) {
viz[src] = true;
q.push_front(src);
list<int>::iterator it;
for (it = G[src].begin(); it != G[src].end(); it++) {
if (viz[*it] == false) {
dfs(*it, viz, G, q);
}
}
}
int main() {
FILE *f = fopen("ctc.in", "r");
FILE *g = fopen("ctc.out", "w");
int n, m;
fscanf(f, "%d%d", &n, &m);
vector<list<int> > G(n);
vector<list<int> > GT(n);
vector<bool> viz1(n, false);
vector<bool> viz2(n, false);
/* for (int i = 0; i < n; i++) {
list<int> l1;
list<int> l2;
G[i].push_back(l1);
GT[i].push_back(l2);
}*/
for (int i = 0; i < m; i++) {
int x1, x2;
fscanf(f, "%d%d", &x1, &x2);
G[x1-1].push_back(x2-1);
GT[x2-1].push_back(x1-1);
}
list<int> queue;
for (int i = 0; i < n; i++) {
if (viz1[i] == false) {
dfs(i, viz1, G, queue);
}
}
list<int>::iterator it;
vector<list<int> > comp;
for (it = queue.begin(); it != queue.end(); it++) {
if (viz2[*it] == false) {
list<int> ctc;
dfs(*it, viz2, GT, ctc);
comp.push_back(ctc);
}
}
fprintf(g, "%d\n", comp.size());
for (int i = 0; i < comp.size(); i++) {
for(it = comp[i].begin(); it != comp[i].end(); it++) {
fprintf(g, "%d ", (*it) + 1);
}
fprintf(g, "\n");
}
fclose(f);
fclose(g);
}