Cod sursa(job #2668360)

Utilizator maria.ianiIani Maria maria.iani Data 4 noiembrie 2020 20:06:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,x,y,i,j;
stack<int> stiva;
vector <int> adj[100001], trans[100001], conex[100001];
int vizitat[100001], nrconex=0;

void dfs(int nod) {
    vizitat[nod]=true;
    for (auto vecin: adj[nod])
        {if (!vizitat[vecin])
             dfs(vecin);}
    stiva.push(nod);
    }

void dfst(int nod)
{
    vizitat[nod]=2;
    conex[nrconex].push_back(nod);
    for (i=0; i<trans[nod].size(); i++)
    {
        if (vizitat[trans[nod][i]]==1)
            dfst(trans[nod][i]);
    }


}
int main()
{
    f>>N>>M;

    for (i=1; i<=M; i++)
        {
            f>>x>>y;
            adj[x].push_back(y);
            trans[y].push_back(x);
        }
    f.close();

    for (i=1; i<=N; i++)
        if (!vizitat[i])
            dfs(i);

    while (stiva.empty()==0)
    {
        int varf=stiva.top();
        if (vizitat[varf]==1)
        {
            nrconex++;
            dfst(varf);
        }
        stiva.pop();
    }

    g<<nrconex<<endl;

    for (i=1; i<=nrconex; i++)
    {
        for (j=0; j<conex[i].size(); j++)
        {
            g<<conex[i][j]<<" ";
        }
        g<<endl;
    }
}