Cod sursa(job #2668770)

Utilizator maria.ianiIani Maria maria.iani Data 5 noiembrie 2020 12:27:00
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack<int> stiva;
vector<int> adj[100001], trans[100001], conex[100001];
int vizitat[100001], nrconex;

void dfs(int nod) 
{
    vizitat[nod]=1;
    for (unsigned int i=0; i<adj[nod].size(); i++)
        {  int vecin=adj[nod][i];
        if (!vizitat[vecin])
            dfs(adj[vecin]);}
    stiva.push(nod);
    }

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

int main()
{   int N,M,x,y;
    f>>N>>M;

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

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

    g<<nrconex<<endl;

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