Cod sursa(job #2924696)

Utilizator Rincu_StefaniaRincu Stefania Rincu_Stefania Data 8 octombrie 2022 19:10:46
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

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

map<int, list<int>> l;
vector<vector<int>> c;
vector<int> vect;
stack<int> s;
struct{
    int ind, pmin;
    bool viz;
    }v[1000];
int cnt;

void ctc(int x)
{
    v[x].ind = cnt;
    v[x].pmin = cnt;
    cnt++;
    int u;
    s.push(x);
    v[x].viz = true;
    for(auto it: l[x])
        if(v[it].ind == -1)
        {
            ctc(it);
            v[x].pmin = min(v[x].pmin, v[it].pmin);
        }
            else if(v[it].viz)
                v[x].pmin = min(v[x].pmin, v[it].ind);
    if(v[x].pmin == v[x].ind)
    {
        vect.clear();
        do
        {
            u = s.top();
            s.pop();
            v[u].viz = false;
            vect.push_back(u);
        }while(x != u);
        c.push_back(vect);
    }
}

int main()
{
    int n, m, x, y, i;
    in>>n>>m;
    while(m)
    {
        in>>x>>y;
        l[x].push_back(y);
        m--;
    }
    for(i = 1; i <= n; i++)
        v[i].ind = -1;
    for(i = 1; i <= n; i++)
        if(v[i].ind == -1)
            ctc(i);
    for(auto it = 0; it < c.size(); it++)
    {
        for(auto it2: c[it])
            out<<it2<<" ";
        out<<endl;
    }
    return 0;
}