Cod sursa(job #2786605)

Utilizator AACthAirinei Andrei Cristian AACth Data 21 octombrie 2021 11:28:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define cin f
#define cout g
//#define int long long
const int Max = 1e5 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
vector < int > v[Max];
vector < int > vt[Max];
int n,m;

void read()
{
    f>>n>>m;
    int i;
    for(i=1;i<=m;i++)
    {
        int n1,n2;
        f>>n1>>n2;
        v[n1].push_back(n2);
        vt[n2].push_back(n1);
    }
}
vector < int > ordine;
int viz[Max];
void dfs(int nod)
{
    if(viz[nod] == 0)
    {

        viz[nod] = 1;
        for(auto vec : v[nod])
            dfs(vec);
        ordine.push_back(nod);
    }
}
int compo[Max];
void baga(int who, int where)
{
    if(compo[who] == 0)
    {
        compo[who] = where;
        for(auto vec : vt[who])
            baga(vec,where);
    }
}
int current_comp_id;
void ctc()
{
    int i;
    current_comp_id = 0;
    for(auto candidat : ordine)
    {
        if(compo[candidat] == 0)
        {
            ++current_comp_id;
            baga(candidat,current_comp_id);
        }
    }
}
void compute_CTC()
{
    int i;
    for(i=1;i<=n;i++)
        if(viz[i] == 0)
        dfs(i);
    reverse(ordine.begin(),ordine.end());
    ctc();
}
vector < vector < int >  > componente;
void solve()
{
    compute_CTC();
    componente.resize(current_comp_id + 1);
    int i;
    for(i=1;i<=n;i++)
        componente[compo[i]].push_back(i);
    cout<<current_comp_id<<'\n';
    for(i=1;i<=current_comp_id;i++)
    {
        for(auto nod : componente[i])
            cout<<nod<<' ';
        cout<<'\n';
    }
}
void restart()
{

}
int32_t main()
{
    nos();

        read();
        solve();
        restart();
    
    return 0;
}