Cod sursa(job #2788739)

Utilizator luciabianca24Tudorache Lucia Bianca luciabianca24 Data 26 octombrie 2021 13:10:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
int n,nrct;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>viz;
vector<vector<int>>g,gt,sol;
stack<int>s;
void citire()
{
    int i1,i2,m;
    fin>>n>>m;
    g=gt=sol=vector<vector<int>>(n+1);
    viz=vector<int>(n+1);
    for(int i=1; i<=m; i++)
    {
        fin>>i1>>i2;
        g[i1].push_back(i2);
        gt[i2].push_back(i1);
    }
}
void dfs(int np)
{
    viz[np]=1;
    for(auto e:g[np])
        if(!viz[e])
            dfs(e);
    s.push(np);
}
void dfst(int np)
{
    viz[np]=2;
    sol[nrct].push_back(np);
    for(auto e:gt[np])
        if(viz[e]==1)
            dfst(e);
}
int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);
    int vf;
    while(!s.empty())
    {
        vf=s.top();
        if(viz[vf]==1)
        {
            nrct++;
            dfst(vf);
        }
        s.pop();
    }
    for(int i=1;i<=nrct;i++)
        sort(sol[i].begin(),sol[i].end());
    fout<<nrct<<'\n';
    for(int i=1;i<=nrct;i++,fout<<'\n')
        for(auto e:sol[i])
        fout<<e<<' ';
}