Pagini recente » Cod sursa (job #73577) | Cod sursa (job #268200) | Cod sursa (job #1028725) | Cod sursa (job #184060) | Cod sursa (job #2927769)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
void CreareGrafSiGrafTranspus(int m, vector<int> listaAdiacentaG[], vector<int> listaAdiacentaGt[]) {
int x, y;
for (int i = 0; i <= m - 1; i++) {
in >> x >> y;
listaAdiacentaG[x].push_back(y);
listaAdiacentaGt[y].push_back(x);
}
}
void DFS_G(int start, int viz[], vector<int> listaAdiacentaG[], stack<int> &stiva) {
viz[start] = 1;
for (auto it = listaAdiacentaG[start].begin(); it!=listaAdiacentaG[start].end(); it++) {
int y = *it;
if (viz[y] == 0)
DFS_G(y, viz, listaAdiacentaG, stiva);
}
stiva.push(start);
}
void DFS_Gt(int start, int viz[], vector<int> listaAdiacentaGt[], vector<int> &parcurgere) {
viz[start] = 1;
parcurgere.push_back(start);
for (auto it = listaAdiacentaGt[start].begin(); it!=listaAdiacentaGt[start].end(); it++) {
int y = *it;
if (viz[y] == 0)
DFS_Gt(y, viz, listaAdiacentaGt, parcurgere);
}
}
int main() {
int m, n;
vector<int> listaAdiacentaG[25001], listaAdiacentaGt[25001];
in >> n >> m;
CreareGrafSiGrafTranspus(m, listaAdiacentaG, listaAdiacentaGt);
stack<int> stiva;
int viz[25001] = {0};
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
DFS_G(i, viz, listaAdiacentaG, stiva);
for (int i = 1; i <= n; i++)
viz[i] = 0;
int nrCompConexe = 0;
vector<vector<int>> compConexe;
while (!stiva.empty()) {
int x = stiva.top();
stiva.pop();
if (viz[x] == 0) {
nrCompConexe++;
vector<int> parcurgere;
DFS_Gt(x, viz, listaAdiacentaGt, parcurgere);
compConexe.push_back(parcurgere);
}
}
out << nrCompConexe << endl;
for (int i = 0; i < nrCompConexe; i++) {
for(auto it = compConexe[i].begin(); it !=compConexe[i].end(); it++)
out << *it << ' ';
out << endl;
}
return 0;
}