Cod sursa(job #2566791)

Utilizator natrovanCeval Marius natrovan Data 3 martie 2020 12:40:46
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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

vector<int>graph[100005];
vector<int>cc[100005];
stack<int>myStack;
int N, M, x, y, ID, visited[100005], id[100005], lowlink[100005], onStack[100005], ccNum;

void tarjanDFS(int thisNode){
    id[thisNode] = lowlink[thisNode] = ++ID;
    myStack.push(thisNode);
    onStack[thisNode] = true; visited[thisNode] = true;

    for(auto nextNode: graph[thisNode]){
        if(!visited[nextNode])
            tarjanDFS(nextNode);
        if(onStack[nextNode])
            lowlink[thisNode] = min(lowlink[thisNode], lowlink[nextNode]);

    }

    if(id[thisNode] == lowlink[thisNode]){
        ccNum++;
        do{
            lowlink[myStack.top()] = id[thisNode];
            cc[ccNum].push_back(myStack.top());
            onStack[myStack.top()] = false;
            myStack.pop();
        }while(myStack.top() != thisNode);
        cc[ccNum].push_back(myStack.top());
        myStack.pop();
    }
}

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        fin >> x >> y;
        graph[x].push_back(y);
    }

    for(int i = 1; i <= N; i++){
        if(!visited[i])
            tarjanDFS(i);
    }

    fout << ccNum << endl;
    for(int i = 1; i <= ccNum; i++){
        for(auto x: cc[i])
            fout << x << ' ';
        fout << endl;
    }

    return 0;
}