Pagini recente » Cod sursa (job #1383481) | Cod sursa (job #290017) | Cod sursa (job #2686185) | Cod sursa (job #854882) | Cod sursa (job #2927763)
#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 (int i = 0; i < listaAdiacentaG[start].size(); i++) {
int y = listaAdiacentaG[start][i];
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 (int i = 0; i < listaAdiacentaGt[start].size(); i++) {
int y = listaAdiacentaGt[start][i];
if (viz[y] == 0)
DFS_Gt(y, viz, listaAdiacentaGt, parcurgere);
}
}
int main() {
int m, n;
vector<int> listaAdiacentaG[10000], listaAdiacentaGt[10000];
in >> n >> m;
CreareGrafSiGrafTranspus(m, listaAdiacentaG, listaAdiacentaGt);
stack<int> stiva;
int viz[10000] = {0};
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
DFS_G(1, 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 (int j = 0; j < compConexe[i].size(); j++)
out << compConexe[i][j] << ' ';
out << endl;
}
return 0;
}