Cod sursa(job #2240121)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 12 septembrie 2018 17:01:31
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

#define MaxN 100005
#define MaxM 200005
#define Finished 2
#define Value1 1

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];
int CTCCount;
int State[MaxN];

void DFS1(int Node) {
    State[Node] = Value1;
    for (auto Vec:Arc[Node])
        if(State[Vec] == 0)
            DFS1(Vec);
}
void DFS2(int Node) {
    State[Node] = Finished;
    CTC[CTCCount].push_back(Node);

    for (auto Vec:ArcT[Node])
        if(State[Vec] == Value1)
            DFS2(Vec);
}

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(State[i+1] != Finished) {
            DFS1(i+1);
            DFS2(i+1);
            CTCCount++;
            for (j=0; j<N; j++)
                if(State[j+1] != Finished)
                    State[j+1] = 0;
        }

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