Cod sursa(job #2570752)

Utilizator sokka1000Ionita Catalin sokka1000 Data 4 martie 2020 19:01:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define nmax 100005

int n,m,x,y,nr;

vector <int > G[nmax],GT[nmax],S,sol[nmax];
bitset <nmax> v;

void dfs(int x)
{
    v[x]=1;
    for(int i=0;i<G[x].size();i++)
    if(v[G[x][i]]==0)
    {
        dfs(G[x][i]);

    }
    S.push_back(x);


}

void dfsGT(int x)
{


    sol[nr].push_back(x);
    v[x]=1;

    for(int i=0;i<GT[x].size();i++)
        if(v[GT[x][i]]==0)
      {
          dfsGT(GT[x][i]);
      }



}



int main()
{
    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);

    }


    for(int i=1;i<=n;i++)
        if(v[i]==0)
        dfs(i);

    v.reset();

    for(int i=n-1;i>=0;i--)
    if(v[S[i]]==0)
    {
        nr++;
        dfsGT(S[i]);

    }


    fout<<nr<<"\n";

    for(int i=1;i<=nr;i++)
    {
        for(int j=0;j<sol[i].size();j++)
           fout<<sol[i][j]<<" ";
           fout<<"\n";

    }



    return 0;
}