Cod sursa(job #2240169)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 12 septembrie 2018 18:23:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

#define MaxN 100005
#define MaxM 200005

std::ifstream InFile("ctc.in");
std::ofstream OutFile("ctc.out");

int N, M;
std::list <int> Arc[MaxN];
std::vector <int> CTC[MaxN];
int CTCCount;
int Ord[MaxN], Low[MaxN];

bool IsStacked[MaxN];
std::stack <int> NodeStack;

int Pasi;
void DFSTarjan(int Node) {
    Ord[Node] = Low[Node] = ++Pasi;

    NodeStack.push(Node);
    IsStacked[Node] = 1;
    for (auto Vec:Arc[Node]) {
        if(Ord[Vec])
            if(IsStacked[Vec])
                Low[Node] = std::min(Low[Node], Ord[Vec]);
            else;
        else
            DFSTarjan(Vec),
            Low[Node] = std::min(Low[Node], Low[Vec]);
    }

    if(Ord[Node] == Low[Node]) {
        int StackTop;
        do {
            StackTop = NodeStack.top();
            NodeStack.pop();
            IsStacked[StackTop] = 0;
            CTC[CTCCount].push_back(StackTop);
        } while(StackTop != Node);
        CTCCount++;
    }
}

void Citire() {
    InFile >> N >> M;
    for (int i=0, x, y; i<M; i++)
        InFile >> x >> y,
        Arc[x].push_back(y);
}

void Rezolvare() {
    for (int i=0, j; i<N; i++)
        if(!Ord[i+1])
            DFSTarjan(i+1);

    OutFile << CTCCount << '\n';
    for (int i=0, j; i<CTCCount; i++) {
        for (j=0; j<CTC[i].size(); j++)
            OutFile << CTC[i][j] << ' ' ;
        OutFile << '\n';
    }
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}