Cod sursa(job #2940312)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 15 noiembrie 2022 11:39:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

stack<int> st;
vector<bool> inst,viz;
vector<vector<int> >sirad,ctc;
vector<int> index,low,c;
int idx,n,m;

void Dfs(int x);
void Tarjan();
int main()
{
    int a,b;
    cin>>n>>m;
    sirad = vector<vector<int>>(n+1);
    index = low = vector<int>(n+1);
    inst = viz = vector<bool>(n+1);


    for(int i=1;i<=m;++i)
    {
        cin>>a>>b;
        sirad[a].push_back(b);
    }

    Tarjan();
    return 0;
}
void Tarjan()
{
    for(int i=1;i<=n;++i)
        if(!viz[i])
        {
            Dfs(i);
        }
    cout<<ctc.size()<<endl;
    for(auto& i : ctc)
        sort(i.begin(),i.end());
    sort(ctc.begin(),ctc.end());
    for(auto i : ctc)
    {
        for(auto j : i)cout<<j<<' ';
        cout<<'\n';
    }
}

void Dfs(int x)
{
    st.push(x);
    inst[x] = true;
    viz[x] = true;
    index[x] = low[x] = ++idx;

    for(auto i : sirad[x])
        if(!viz[i])
        {
            Dfs(i);
            low[x] = min(low[x],low[i]);
        }
        else if(inst[i])low[x] = min(low[x],index[i]);

    if(index[x] == low[x])
    {
        c.clear();
        while(!st.empty())
        {
            int a = st.top();
            st.pop();
            inst[a] = false;
            c.push_back(a);
            if(index[a] == low[a])break;
        }
        ctc.push_back(c);
    }
}