Cod sursa(job #2926866)

Utilizator dragosteleagaDragos Teleaga dragosteleaga Data 18 octombrie 2022 20:56:26
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream o("ctc.out");
int numarNoduri,numarMuchii,x,y,id=0,sscCount=0;
vector<int>la[6000];
vector<int>ids(6000,-1);
vector<int>low(6000,0);
vector<bool>onStack(6000,false);
vector<int>raspuns[6];
stack<int>myStack;
void DFS(int at){
    myStack.push(at);
    onStack[at]=true;
    ids[at]=low[at]=id++;
    for(auto to:la[at])
    {
        if(ids[to]==-1)
            DFS(to);
        if(onStack[to])
            low[at]=min(low[at],low[to]);

    }
    if(ids[at]==low[at]){
        int node=myStack.top();
        myStack.pop();


        while(node!=at){
            raspuns[sscCount].push_back(node);
            onStack[node]=false;
            low[node]=ids[at];
             node=myStack.top();
            myStack.pop();
        }
        onStack[node]=false;
        low[node]=ids[at];
        raspuns[sscCount].push_back(node);
        sscCount++;
    }
}
void findSccs(){
    for(int i=1;i<=numarNoduri;i++)
        if(ids[i]==-1)
            DFS(i);

}
int main() {
    f>>numarNoduri>>numarMuchii;

    while(f>>x&&f>>y)
        la[x].push_back(y);
    findSccs();
    o<<sscCount<<"\n";
    for(int i=0;i<sscCount;i++){
        sort(raspuns[i].begin(),raspuns[i].end());
        for(auto a:raspuns[i])
            o<<a<<" ";
        o<<endl;
    }




    return 0;
}