Cod sursa(job #2928799)

Utilizator alexutzIstrate Cristian Alexandru alexutz Data 23 octombrie 2022 21:40:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

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


int n,m;
vector<vector<int>> la;
vector<vector<int>> raspuns;




stack<int> stiva;
int low[100001],viz[100001],ctc[100001];
int id=1;

void citire()
{
    f>>n>>m;

    int i,x,y;
    for(i=0;i<=n;i++)
    {
        vector<int> aux;
        la.push_back(aux);
    }

    for(i=1;i<=m;i++)
    {
        f >> x >> y;
        la[x].push_back(y);
    }

    for(i=1;i<=n;i++)
        sort(la[i].begin(),la[i].end());

}

void dfs(int curent)
{

    stiva.push(curent);
    low[curent] = viz[curent] = id;
    ctc[curent] = 1;
    id++;


    int i,l,dest,aux;
    l = la[curent].size();
    for(i=0;i<l;i++)
    {
        dest = la[curent][i];
        if(viz[dest] == 0)
            dfs(dest);
        if(ctc[dest]==1)
            low[curent] = min(low[curent],viz[dest]);
    }

    if(viz[curent] == low[curent])
    {

        vector<int> octc;
        aux = stiva.top();
        ctc[aux]=0;
        octc.push_back(aux);
        stiva.pop();

        while(aux != curent)
        {
            aux = stiva.top();
            ctc[aux]=0;
            octc.push_back(aux);
            stiva.pop();
        }

        raspuns.push_back(octc);
    }

}

void rezolvare()
{
    int i;
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i);
}




void afisare_raspuns()
{
    int i,j,l,rasp_size = raspuns.size();
    g << rasp_size << endl;
    //cout << rasp_size << endl;
    for(i=0;i<rasp_size;i++)
    {
        l = raspuns[i].size();
        for(j=0;j<l;j++)
        {
            g << raspuns[i][j] << " ";
            //cout << raspuns[i][j] << " ";
        }
        g << endl;
        //cout << endl;
    }

}



int main()
{
    citire();
    rezolvare();
    afisare_raspuns();




}