Cod sursa(job #2695199)

Utilizator Edwuard99Diaconescu Vlad Edwuard99 Data 12 ianuarie 2021 01:15:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb

# include <cstdio>
# include <vector>
 
using namespace std;
 
# define FIN "ctc.in"
# define FOUT "ctc.out"
# define min(a, b) (a < b ? a : b)
# define MAXN 100005
 
int N, M, i, vf, ct, Time;
int St[MAXN];
int Lvl[MAXN];
int Low[MAXN];
vector <int> G[MAXN];
vector <int> CTC[MAXN];
 
     void Dfs(int nod)
     {
         vector <int> :: iterator it;
         
         St[++vf] = nod;
         Lvl[nod] = Low[nod] = ++Time;
         for (it = G[nod].begin(); it != G[nod].end(); ++it)
         {
             if (!Lvl[*it])
             {
                Dfs(*it);
                Low[nod] = min(Low[nod], Low[*it]);
             } else
             if (Lvl[*it] > 0)
                Low[nod] = min(Low[nod], Lvl[*it]);
         }
         
         if (Low[nod] == Lvl[nod])
           {
              ++ct;
              for (i = vf; St[i + 1] != nod; --i)
              {
                 CTC[ct].push_back(St[i]);
                 Lvl[St[i]] = -1;
              }
              vf = i;
           }
     }
 
     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf("%d %d",&N, &M);
         for (i = 1; i <= M; ++i)
         {
             int x, y;
             scanf("%d %d",&x, &y);
             
             G[x].push_back(y);
         }
         
         vf = ct = Time = 0;
         for (i = 1; i <= N; ++i)
           if (!Lvl[i]) Dfs(i);
         
         printf("%d\n",ct);
         
         vector <int> :: iterator it;
         for (i = 1; i <= ct; ++i)
         {
             for (it = CTC[i].begin(); it != CTC[i].end(); ++it)
                printf("%d ",*it);
             printf("\n");
         }
         
         return 0;
     }