Cod sursa(job #3328377)

Utilizator DariuzzHackerPrime Dariuzz Data 8 decembrie 2025 10:56:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std ; 
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int seen[10000001] , viz[1000001] ; 
stack<int> rez ; 
void dfs1(int start , vector<vector<int> >&G ){
        seen[start] = 1 ; 
          for(int j = 0 ; j < G[start].size() ; j ++) {
                int nei = G[start][j];
                 if(!seen[nei])
                 {
                    dfs1(nei,G);
                 }
          }
        rez.push(start);
}
void dfs2(int start , vector<vector<int> >&GT , vector<int>&path){
       if(!viz[start])
         path.push_back(start);
        viz[start] = 1 ; 
     for(int j = 0 ; j < GT[start].size() ; j ++ ){
            int nei = GT[start][j];
              if(!viz[nei]){
                   dfs2(nei,GT,path);
              }
     }
}
int main(){


      int n , m ; 
       cin>>n>>m;
         vector<vector<int> > G(n+1) , GT(n+1);
        int x , y ; 
          for(int i = 1 ; i <= m ; i ++ )
          {
               cin>>x>>y;
               G[x].push_back(y);
               GT[y].push_back(x);
          }
            for(int i =1 ; i <= n ; i ++ )
              if(!seen[i])
                dfs1(i,G);
        vector<vector<int> > conex ; 
       while(!rez.empty()){
           int nod = rez.top();
              vector<int> path ;
              if(!viz[nod]){
                  dfs2(nod,GT,path);
                conex.push_back(path); 
              }



            rez.pop();
       }
        sort(conex.begin(),conex.end());
         cout<<conex.size()<<'\n';
           for(int i = 0 ; i < conex.size() ; i ++ )
           {
              
               sort(conex[i].begin(),conex[i].end());
                 for(int j = 0 ; j < conex[i].size() ; j ++ )
                   cout<<conex[i][j]<< ' ';
                   cout<<'\n';
           }





      return 0 ; 
}