Pagini recente » Cod sursa (job #2785084) | Cod sursa (job #1182305) | Cod sursa (job #10137) | Cod sursa (job #2565451) | Cod sursa (job #2929512)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
void creategraph(int m, vector<int> lista_g[], vector<int> lista_gt[]) { //creeam graful si graful transpus
int x, y;
for (int i = 0; i <= m - 1; i++) {
in >> x >> y;
lista_g[x].push_back(y);
lista_gt[y].push_back(x);
}
}
void DFS_G(int start, int viz[], vector<int> lista_g[], stack<int> &stiva) {
viz[start] = 1;
for (auto it = lista_g[start].begin(); it!=lista_g[start].end(); it++) {
int y = *it;
if (viz[y] == 0)
DFS_G(y, viz, lista_g, stiva);
}
stiva.push(start);
}
void DFS_Gt(int start, int viz[], vector<int> lista_gt[], vector<int> &parcurgere) {
viz[start] = 1;
parcurgere.push_back(start);
for (auto it = lista_gt[start].begin(); it!=lista_gt[start].end(); it++) {
int y = *it;
if (viz[y] == 0)
DFS_Gt(y, viz, lista_gt, parcurgere);
}
}
int main() {
int m, n;
vector<int> lista_g[100001], lista_gt[100001];
in >> n >> m;
creategraph(m, lista_g, lista_gt);
stack<int> stiva;
int viz[100001] = {0};
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
DFS_G(i, viz, lista_g, stiva);
for (int i = 1; i <= n; i++)
viz[i] = 0;
int nr_cc = 0;//nr comp conexe
vector<vector<int>> comp_c;//comp conexe
while (!stiva.empty()) {
int x = stiva.top();
stiva.pop();
if (viz[x] == 0) {
nr_cc++;
vector<int> parcurgere;
DFS_Gt(x, viz, lista_gt, parcurgere);
comp_c.push_back(parcurgere);
}
}
out << nr_cc << endl;
for (int i = 0; i < nr_cc; i++) {
for(auto it = comp_c[i].begin(); it !=comp_c[i].end(); it++)
out << *it << ' ';
out << endl;
}
return 0;
}