Pagini recente » Monitorul de evaluare | Diferente pentru arhiva-educationala intre reviziile 12 si 13 | Rezultatele filtrării | Diferente pentru implica-te/arhiva-educationala intre reviziile 201 si 223 | Cod sursa (job #235556)
Cod sursa(job #235556)
# include <cstdio>
# include <vector>
using namespace std;
# define FIN "ctc.in"
# define FOUT "ctc.out"
# define MAXN 100005
int N, M, i, comp, ct, L, j;
int S[MAXN];
int FT[MAXN];
vector <int> E1[MAXN];
vector <int> E2[MAXN];
vector <int> CTC[MAXN];
void df1(int nod)
{
int i, L = E1[nod].size();
S[nod] = 1;
for (i = 0; i < L; ++i)
if (!S[E1[nod][i]]) df1(E1[nod][i]);
FT[++ct] = nod;
}
void df2(int nod, int comp)
{
int i, L = E2[nod].size();
S[nod] = 2; CTC[comp].push_back(nod);
for (i = 0; i < L; ++i)
if (S[E2[nod][i]] != 2) df2(E2[nod][i], comp);
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d%d",&N,&M);
int a, b;
for (i = 1; i <= M; ++i)
{
scanf("%d%d",&a, &b);
E1[a].push_back(b);
E2[b].push_back(a);
}
ct = 0;
for (i = 1; i <= N; ++i)
if (!S[i]) df1(i);
comp = 0;
for (i = ct; i >= 1; --i)
if (S[FT[i]] != 2) df2(FT[i], ++comp);
printf("%d\n",comp);
for (i = 1; i <= comp; ++i)
{
L = CTC[i].size();
for (j = 0; j < L; ++j)
printf("%d ",CTC[i][j]);
printf("\n");
}
return 0;
}