Cod sursa(job #3215665)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 15 martie 2024 11:26:58
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,indecs,instack[100001],idx[100001],lowlink[100001],ctc;
vector<int> G[100001],cc[100001];
stack<int> S;
void tarjan(int nod, int& ctc)
{
    idx[nod]=lowlink[nod]=indecs;
    indecs++;
    S.push(nod);
    instack[nod]=1;

    for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
    {
        if(idx[*it]==-1)
        {
            tarjan(*it,ctc);
            lowlink[nod]=min(lowlink[nod],lowlink[*it]);
        }
        else
            lowlink[nod]=min(lowlink[nod],lowlink[*it]);
    }

    if(idx[nod]==lowlink[nod])
    {
        while(S.top()!=nod)
        {
            instack[S.top()]=0;
            cc[ctc].push_back(S.top());
            S.pop();
        }
        instack[nod]=0;
        cc[ctc].push_back(nod);
        ctc++;
        S.pop();
    }
}
int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin >> x >> y;
        G[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        idx[i]=-1;
        lowlink[i]=0;
    }
    indecs=1;
    ctc=1;
    for(int i=1;i<=n;i++)
    {
        if(idx[i]==-1)
        {
            tarjan(i,ctc);
        }
    }
    fout << ctc-1 << "\n";
    for(int i=1;i<ctc;i++)
    {
        for(vector<int>::iterator it=cc[i].begin();it!=cc[i].end();++it)
            fout << *it << " ";
        fout << "\n";
    }
    return 0;
}