Cod sursa(job #235556)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 24 decembrie 2008 14:20:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
# 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;
    }