Pagini recente » infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #392504) | Cod sursa (job #853221) | Cod sursa (job #1686391) | Cod sursa (job #3207294)
/*
Fie un graf orientat G = (V, E), memorat prin intermediul matricei de adiacenta, si un nod i.
Afisati componenta tare conexa careia ii apartine acesta.
Ex:
5
1 2
1 4
2 3
3 1
4 5
5 4
Input: nodul 1: 1, 2, 3
nodul 2: 1, 2, 3
nodul 3: 1, 2, 3
nodul 4: 4, 5
nodul 5: 4, 5
*/
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, nr_componente = 0, matrix[10001][10001];
int pred[1001], succ[1001], marcat[1001];
int componente[10001][10001];
void citire() {
fin >> n >> m;
int x, y;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
matrix[x][y] = 1;
}
}
void dfs_succ(int node) {
succ[node] = 1;
for (int i = 1; i <= n; i++)
if (matrix[node][i] && !succ[i])
dfs_succ(i);
}
void dfs_prec(int node) {
pred[node] = 1;
for (int i = 1; i <= n; i++)
if (matrix[i][node] && !pred[i])
dfs_prec(i);
}
void reset() {
for (int i = 1; i <= n; i++) succ[i] = pred[i] = 0;
}
void tare_conex(int node) {
nr_componente++;
dfs_prec(node);
dfs_succ(node);
for (int i = 1; i <= n; i++)
if (succ[i] && pred[i]) {
componente[nr_componente][i] = 1;
marcat[i] = 1;
}
reset();
}
int main() {
citire();
for (int node = 1; node <= n; node++)
if (!marcat[node])
tare_conex(node);
fout << nr_componente << '\n';
for (int i = 1; i <= nr_componente; i++) {
for (int j = 1; j <= n; j++)
if (componente[i][j] == 1)
fout << j << " ";
fout << '\n';
}
return 0;
}