Pagini recente » Cod sursa (job #2185656) | Cod sursa (job #1463927) | Cod sursa (job #2093334) | Cod sursa (job #2066977) | Cod sursa (job #2240074)
#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;
}