Pagini recente » Cod sursa (job #2202840) | Cod sursa (job #1122275) | Cod sursa (job #2849529) | Cod sursa (job #2134856) | Cod sursa (job #2925519)
/*
Link: https://www.infoarena.ro/problema/ctc
Idee: Am aplicat algoritmul lui Tarjan
Complexitate: O(n + m)
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define dim 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b, cnt = 0, id = 0;
vector< vector<int> > lists(dim);
vector<bool> onStack(dim); //verificam mai usor existenta pe stiva
vector<int> low(dim), disc(dim); //vectorii de low-key si dicover
stack<int> stk; //stiva necesara obtinerii corecte a componentelor
vector< vector<int> > sol(dim);
/*
Fiecare nod parcurs e pus pe stiva si initiala lui valoare low-key este cea de discover.
Aplicam acelasi lucru si pt vecini, pana ajungem la smecheria algoritmului:
-cand suntem pe o muchie de intoarcere, actualizam low-key ul nodului curent
dupa formula 'low[nod] = min(low[nod], low[vecin])', DOAR DACA vecinul se afla pe stiva,
adica este valid pt componenta actuala ( din el se poate ajunge la nodul curent )
-cand epuizam vecinii unui nod, verificam daca am inchis o componenta, conditia de inchidere
fiind 'disc[nod] == low[nod]'. Daca da, scoatem de pe stiva toate nodurile pana ajungem la cel
curent (noduri care alcatuiesc componenta tare conexa), si le actualizam low-key ul, ca se le
grupam la final
*/
void tarjan(int nod) {
stk.push(nod);
onStack[nod] = true;
disc[nod] = low[nod] = ++id;
for (int i = 0; i < lists[nod].size(); i++) {
int vecin = lists[nod][i];
if (disc[vecin] == 0) {
tarjan(vecin);
}
if( onStack[vecin] ) {
low[nod] = min(low[nod], low[vecin]);
}
}
if (disc[nod] == low[nod]) {
while (stk.top() != nod) {
onStack[stk.top()] = false;
low[stk.top()] = disc[nod];
stk.pop();
}
onStack[stk.top()] = false;
low[stk.top()] = disc[nod];
stk.pop();
cnt++;
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> a >> b;
lists[a].push_back(b);
}
for (int i = 1; i <= n; i++) {
if (disc[i] == 0) {
tarjan(i);
}
}
for(int i = 1; i <= n; i++)
sol[ low[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';
}
}
return 0;
}