Cod sursa(job #2983820)

Utilizator LupuRaduLupu Sebastian-Radu LupuRadu Data 23 februarie 2023 09:22:22
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int> > G, GT;

int n , m , contor , nrs,cnt;
int v[1005][1005];
vector<bool> V;
vector<int> S;

void read()
{
    fin >> n >> m;
    G = GT = vector<vector<int>>(n + 1);
    for(int i = 1 ; i <= m ; i++)
    {
        int a , b;
        fin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }

}

void dfs(int k)
{
    V[k] = true;
    for(auto x : G[k])
        if(!V[x])
            dfs(x);
    S.push_back(k);
}

void dfsGT(int k)
{
    V[k]=1;v[contor][cnt]=k;
    for(auto x: GT[k])
        if(! V[x])
            cnt++,dfsGT(x);

}

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 ++;cnt=1;
                dfsGT(*it);
                v[contor][0]=cnt;
        }

    fout<<contor<<endl;
    for(int i=1;i<=contor;i++)
        {for(int j=1;j<=v[i][0];j++)
            fout<<v[i][j]<<" ";
        fout<<endl;
        }
    return 0;
}