Pagini recente » Cod sursa (job #2539531) | Cod sursa (job #2230512) | Cod sursa (job #2461626) | Cod sursa (job #1090768) | Cod sursa (job #2926494)
#include <iostream>
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
/// Vom folosi algoritmul lui Tarjan
vector < vector <int> > la(N), sol(N); /// matricea de adiacenta si lista de solutii
vector <int> lowLink(N), disc(N), stkItem(N); /// lowLink[i] = x --> x e cel mai mic nod la care ajunge nodul i prin DFS
stack <int> stk; /// adaugam nodurile valide pe masura ce parcugem cu DFS, nodurile sunt eliminate de fiecare data cand s a gasit
/// o SCC
int n, m, x, y, i, j, cnt, g;
void Citire(){
fin >> n >> m;
for(i=1; i<=m; i++)
{
fin >> x >> y;
la[x].push_back(y);
}
}
void findComponent(int node) {
stk.push(node);
stkItem[node] = 1;
disc[node] = lowLink[node] = ++g;
///parcurgem fiecare lista
for (int i = 0; i < la[node].size(); i++) {
int x = la[node][i];
///inseamna ca trebuie sa ii gasim componenta
if (disc[x] == -1) {
findComponent(x);
}
/// actualizam cel mai mic nod la care poate ajunge node cu un alt posibil candidat, valoarea
/// pe care deja o are sau valoarea pe care o afla nodul incident
if( stkItem[x] != 0 ) {
lowLink[node] = min(lowLink[node], lowLink[x]);
}
}
/// daca, componenta actuala a fost "inchisa", le dam pop din stiva pana ajungem inapoi la nodul de unde am plecat
/// facem stkItem = 0 ca sa le punem in solutia finala
int poppedItem = 0;
if (disc[node] == lowLink[node]) {
while (stk.top() != node) {
poppedItem = stk.top();
stkItem[poppedItem] = 0;
lowLink[poppedItem] = disc[node];
stk.pop();
}
poppedItem = stk.top();
stkItem[poppedItem] = 0;
lowLink[poppedItem] = disc[node];
stk.pop();
cnt++;
}
}
void WriteSol(){
for(int i = 1; i <= n; i++)
sol[ lowLink[i] ].push_back(i);
fout << cnt << '\n';
for(int i = 1; i <= n; i++) {
if( sol[i].size() ) {
for(int j = 0; j < sol[i].size(); j++) {
fout << sol[i][j] << " ";
}
fout << '\n';
}
}
}
int main()
{
Citire();
for(i=1; i<=n; i++)
disc[i] = lowLink[i] = -1;
for(i=1; i<=n; i++)
if(disc[i] == -1)
findComponent(i);
WriteSol();
return 0;
}