Cod sursa(job #3000672)

Utilizator AndreiStreheStreche Andrei Claudiu AndreiStrehe Data 12 martie 2023 18:46:50
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

#define nmax 100001
vector <int> a[nmax];
vector <int> transpusa[nmax];
vector <int> rez[nmax];
stack <int> st;

int viz[nmax];
int vecin,nodcurent,n,m,i,k1,k2,nrc,x,j,q;

void  dfs(int nodcurent)
{
    viz[vecin]=1;
    for(int i=0;i<a[nodcurent].size();i++)
    {
        vecin=a[nodcurent][i];
        if(viz[vecin]==0)
            dfs(vecin);
    }
    st.push(nodcurent);
}
void tconexe(int q)
{
    viz[q]=2;
    rez[nrc].push_back(q);

    for(int i=0;i<transpusa[q].size();i++)
    {
        vecin=transpusa[q][i];
        if(viz[vecin]==1)
            tconexe(vecin);
    }


}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>k1>>k2;
        a[k1].push_back(k2);
        transpusa[k2].push_back(k1);
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i);

    while(st.empty()==0)
    {
        x=st.top();
        if(viz[x]==1)
        {
            nrc++;
            tconexe(x);
        }
        st.pop();
    }
    g<<nrc<<endl;
    for(i=1;i<=nrc;i++)
    {
        for(j=0;j<rez[i].size();j++)
            g<<rez[i][j]<<" ";
        g<<endl;
    }

    return 0;
}