Cod sursa(job #2240149)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 12 septembrie 2018 17:45:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 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], ArcT[MaxN];
std::vector <int> CTC[MaxN];
std::stack <int> OrderStack;
int CTCCount;
bool Seen[MaxN];

void DFS1(int Node) {
    Seen[Node] = 1;
    for (auto Vec:Arc[Node])
        if(!Seen[Vec])
            DFS1(Vec);
    OrderStack.push(Node);
}
void DFS2(int Node) {
    Seen[Node] = 1;
    for (auto Vec:ArcT[Node])
        if(!Seen[Vec])
            DFS2(Vec);
    CTC[CTCCount].push_back(Node);
}

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

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

    for (int i=0, j; i<N; i++)
        Seen[i+1] = 0;

    int StackTop;
    while(!OrderStack.empty()) {
        StackTop = OrderStack.top();
        OrderStack.pop();

        if(!Seen[StackTop])
            DFS2(StackTop),
            CTCCount++;
    }

    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;
}