Cod sursa(job #2926934)

Utilizator RosianuRobertRosianu Robert RosianuRobert Data 18 octombrie 2022 22:28:19
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,nrN,nrM,op,x,y,k=0,ctc=0,inde=0;
vector<int>lowlink(100001);
vector<int> ind(100001);
stack<int> q;
vector<int>inds(100001,0);
vector<vector<int>> lista(10001);
vector<bool>verif(100001,false);
vector<int> rasp[100001];
void df(int nod)
{
    q.push(nod);
    verif[nod] = true;
    lowlink[nod] = inde+1;
    inds[nod] = inde+1;
    inde = inde
+1;
    for(auto p:lista[nod])
    {
        if(!inds[p])
            df(p);
        if(verif[p])
            lowlink[nod] = min(lowlink[nod],lowlink[p]);
    }
    if(inds[nod] == lowlink[nod])
    {
        rasp[ctc].push_back(nod);
        int node = q.top();
        q.pop();
        verif[node] = false;
        while(node!=nod)
        {
            rasp[ctc].push_back(node);
            verif[node] = false;
            lowlink[node] = inds[nod];
            node = q.top();
            q.pop();
        }
        ctc++;
    }
}
void succesor()
{
    for(int i=1; i<=nrN; i++)
        if(!inds[i])
            df(i);
}
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>nrN>>nrM;
    for(int i=1; i<=nrM; i++)
    {
        f>>x>>y;
        lista[x].push_back(y);
    }
    succesor();
    g<<ctc<<endl;
    //cout<<ctc<<" ";
    for(int i=0; i<ctc; i++)
    {
        for(int j=0; j<rasp[i].size(); j++)
            g<<rasp[i][j]<<" ";
        g<<endl;
    }
    return 0;
}