Pagini recente » Cod sursa (job #1242142) | Cod sursa (job #2743424) | Cod sursa (job #1376732) | Cod sursa (job #2941257) | Cod sursa (job #477158)
Cod sursa(job #477158)
//O(N^3)
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 128
int D[NMAX][NMAX], viz[NMAX], n, m, nr_sol;
vector <int> G[NMAX], sol[NMAX];
void read ();
void roy_floyd ();
void DFS ();
void components ();
void print_sol ();
int main () {
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
read ();
roy_floyd ();
components ();
print_sol ();
return 0;
}
void read () {
int i, x, y;
scanf ("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
D[x][y] = 1;
}
}
void roy_floyd () {
int k, i, j;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if ((!D[i][j] || D[i][k] + D[k][j] < D[i][j]) && i != j && i != k && k != j && D[i][k] && D[k][j])
D[i][j] = D[i][k] + D[k][j];
}
void DFS (int nod) {
int i;
viz[nod] = 1; sol[nr_sol].push_back (nod);
for (i = 1; i < (int) G[nod].size(); i++)
if (!viz[ G[nod][i] ])
DFS (G[nod][i]);
}
void components () {
int i, j;
for (i = 2; i <= n; i++)
for (j = 1; j < i; j++)
if (D[i][j] && D[j][i]) {
G[i].push_back (j);
G[j].push_back (i);
}
for (i = 1; i <= n; i++)
if (!viz[i]) {
nr_sol++;
DFS (i);
}
}
void print_sol () {
int i, j;
printf ("%d\n", nr_sol);
for (i = 1; i <= nr_sol; i++) {
for (j = 0; j < (int) sol[i].size(); j++)
printf ("%d ", sol[i][j]);
printf ("\n");
}
}