Mai intai trebuie sa te autentifici.
Cod sursa(job #385743)
| Utilizator | Data | 23 ianuarie 2010 13:26:51 | |
|---|---|---|---|
| Problema | Componente tare conexe | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.94 kb |
#include <stdio.h>
#include <vector>
using namespace std;
const int n_max = 100001;
vector <int> v[n_max],
c[n_max];
int r[n_max],
d[n_max],
viz[n_max];
int time = 0, k = 0, n, m;
void df(int x)
{
vector <int>::iterator it;
viz[x] = 1;
++time;
d[x] = time; //Depth
r[x] = time; //Reach
for (it = v[x].begin(); it!=v[x].end(); ++ it)
{
if (!viz[*it])
{
df(*it);
r[x] = min(r[x],r[*it]);
}
else
r[x] = min(r[x],r[*it]);
}
c[k].push_back(x);
if (d[x] == r[x])
++k;
}
int main()
{
int a,b;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++ i)
{
scanf("%d %d", &a, &b);
v[a].push_back(b);
}
for (int i = 1; i <= n; ++ i)
if (!viz[i])
df(i);
printf("%d\n", k);
for (int i = 0; i < k; ++ i, printf("\n"))
for (int j = 0; j < c[i].size(); ++ j)
printf("%d ", c[i][j]);
return 0;
}