Cod sursa(job #2870928)

Utilizator dianannnDiana Novac dianannn Data 12 martie 2022 18:35:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
#define nmax 100005
vector<int>a[nmax],gt[nmax],ctc[nmax];
int n,m,contor,nrs,nr_ctc;
vector<bool>v;
vector<int>s;
void read()
     {
         f>>n>>m;
         for(int i=1;i<=m;i++)
         {
             int x,y;
             f>>x>>y;
             a[x].push_back(y);
             gt[y].push_back(x);
         }
     }
void dfs(int k)
    {
        v[k]=true;
        for(auto u:a[k])
             if(!v[u])
                dfs(u);
        s.push_back(k);
    }
void dfs_gt(int k)
     {
         v[k]=true;
         ctc[contor].push_back(k);
         for(auto u:gt[k])
              if(!v[u])
                 dfs_gt(u);
     }

int main()
{
    read();
    v=vector<bool>(n+1,false);
    for(int i=1;i<=n;i++)
         if(!v[i])
            dfs(i);
    v=vector<bool>(n+1,false);
    for (vector<int>::reverse_iterator it=s.rbegin();it!=s.rend();it++)
        if(!v[*it])
            {
            contor++;
            dfs_gt(*it);
            }
    g<<contor<<'\n';
    for(int i=1;i<=contor;i++)
        {
        for(int j=0;j<ctc[i].size();j++)
            g<<ctc[i][j]<<" ";
        g<<'\n';
        }
    return 0;
}