Cod sursa(job #3170727)

Utilizator AlexandruDrg23Draghici Alexandru AlexandruDrg23 Data 18 noiembrie 2023 08:28:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int MAXI=100000;

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


vector<vector<int>> ma,ctc;
vector<int> idx(MAXI+1,0),mini(MAXI+1,0);
vector<bool> inst(MAXI+1,false);
stack<int> s;
int timp=1;
int tot=0;

void trj(int nod)
{
    mini[nod]=timp;
    idx[nod]=timp;
    timp++;
    s.push(nod);
    inst[nod]=true;
    vector<int>::iterator el;
    for(el=ma[nod].begin();el!=ma[nod].end();el++)
    {
        if(idx[*el]==0)
        {
            trj(*el);
            mini[nod]=min(mini[nod],mini[*el]);
        }
        else if(inst[*el]==true)
            mini[nod]=min(mini[nod],mini[*el]);
    }
    if(idx[nod]==mini[nod])
    {
        int n;
        vector<int> conex;
        do
        {
            n=s.top();
            s.pop();
            inst[n]=false;
            conex.push_back(n);
        } while(n!=nod);
        ctc.push_back(conex);
        tot++;
    }
}


int main()
{
    int n,m,x,y;
    fin>>n>>m;
    ma.resize(n+1);
    for(int k=1;k<=m;k++)
    {
        fin>>x>>y;
        ma[x].push_back(y);
    }
    for(int k=1;k<=n;k++)
    {
        if(idx[k]==0)
            trj(k);
    }
    vector<vector<int>>::iterator el;
    vector<int>::iterator k;
    fout<<tot<<'\n';
    for(el=ctc.begin();el!=ctc.end();el++)
    {
        for(k=el->begin();k!=el->end();k++)
            fout<<*k<<" ";
        fout<<'\n';
    }
    return 0;
}