Pagini recente » Cod sursa (job #1515048) | Cod sursa (job #1844876) | Istoria paginii utilizator/milervladut | Cod sursa (job #2780064) | Cod sursa (job #770764)
Cod sursa(job #770764)
/*
Componente tare conexe.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#define MAXN 100050
using namespace std;
int nr_noduri, nr_muchii, nr_comp_conexe, dim;
vector<int> graf_init[MAXN], graf_transpus[MAXN], componente[MAXN];
int stiva[MAXN], vizitat[MAXN], marcat[MAXN];
void df_graf_init (int u) {
int i;
vizitat[u] = 1;
for (i = 0; i < graf_init[u].size(); i++)
if (!vizitat[graf_init[u][i]])
df_graf_init(graf_init[u][i]);
stiva[++dim] = u;
}
void df_graf_transpus (int u, int idx_comp) {
int i;
marcat[u] = idx_comp;
for (i = 0; i < graf_transpus[u].size(); i++)
if (!marcat[graf_transpus[u][i]])
df_graf_transpus(graf_transpus[u][i], idx_comp);
}
int main () {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i, j, x, y;
scanf("%d %d", &nr_noduri, &nr_muchii);
for (i = 1; i <= nr_muchii; i++) {
scanf("%d %d", &x, &y);
graf_init[x].push_back(y);
graf_transpus[y].push_back(x);
}
for (i = 1; i <= nr_noduri; i++)
if (!vizitat[i])
df_graf_init(i);
nr_comp_conexe = 0;
while (dim) {
if (!marcat[stiva[dim]]) {
nr_comp_conexe++;
df_graf_transpus(stiva[dim], nr_comp_conexe);
}
stiva[dim--];
}
for (i = 1; i <= nr_noduri; i++)
componente[marcat[i]].push_back(i);
printf("%d\n", nr_comp_conexe);
for (i = 1; i <= nr_comp_conexe; i++) {
for (j = 0; j < componente[i].size(); j++)
printf("%d ", componente[i][j]);
printf("\n");
}
return 0;
}