Cod sursa(job #2240074)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 12 septembrie 2018 12:42:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

#define MaxN 100005
#define MaxM 200005

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

// Liste de adiacenta alocate static
int N, M;
int Start[MaxN],
    StartT[MaxN];
int Adc[2][MaxM],
    AdcT[2][MaxM];
std::vector <int> CTCMembers[MaxN];
int CTCCount;

int Mark[MaxN];

void DFS(int Node, int Adc[][MaxM], int Start[], int Value) {
    Mark[Node] += Value;

    int p = Start[Node];
    while(p) {
        if(Mark[Adc[0][p]] < Value)
            DFS(Adc[0][p], Adc, Start, Value);
        p = Adc[1][p];
    }
}

void FindCTC(int Index) {
    DFS(Index, Adc, Start, 1);
    DFS(Index, AdcT, StartT, 2);

    for (int i=0; i<N; i++) {
        if(Mark[i+1] == 3)
            Mark[i+1] = 4,
            CTCMembers[CTCCount].push_back(i+1);
        else Mark[i+1] = 0;
    }   CTCCount ++;
}

void Register(int x, int y, int Adc[][MaxM], int Start[], int Index) {
    Adc[0][Index] = y;
    Adc[1][Index] = Start[x];
    Start[x] = Index;
}

void Citire() {
    InFile >> N >> M ;
    for (int i=0, x, y; i<M; i++) {
        InFile >> x >> y;
        Register(x, y, Adc, Start, i+1);
        Register(y, x, AdcT, StartT, i+1);
    }
}

void Rezolvare() {
    for (int i=0; i<N; i++)
        if (!Mark[i+1])
            FindCTC(i+1);

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

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

    return 0;
}