Cod sursa(job #3213196)

Utilizator Simon2712Simon Slanina Simon2712 Data 12 martie 2024 17:58:16
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N=100001;
vector<int> graf[N];
vector<int> graftrans[N];
int vc[N],k;
vector<int> v;
vector<int> matrez[N];
void dfs(int nod)
{
    int i;
    vc[nod]=1;
    v.push_back(nod);
    int m=graf[nod].size();
    int nod2;
    for(i=0;i<m;i++)
    {
        nod2=graf[nod][i];
        if(!vc[nod2])
            dfs(nod2);
    }
}
void dfstranspus(int nod)
{
    int nod2;
    vc[nod]=1;
    matrez[k].push_back(nod);
    int m=graftrans[nod].size();
    for(int i=0;i<m;i++)
    {
        nod2=graftrans[nod][i];
        if(!vc[nod2])
            dfstranspus(nod2);
    }
}
int main()
{
    int n,m,i,x,y,ctcsize,j;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        graf[x].push_back(y);
        graftrans[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(!vc[i])
        {

            dfs(i);
        }
    }
    for(i=1;i<=n;i++)
        vc[i]=0;
    for(i=n-1;i>0;i--)
    {
        if(!vc[v[i]])
        {
            k++;
            dfstranspus(v[i]);
        }
    }
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        ctcsize=matrez[i].size();
        for(j=0;j<ctcsize;j++)
            fout<<matrez[i][j]<<" ";
        fout<<'\n';
    }
    return 0;
}