Pagini recente » Cod sursa (job #1044881) | Cod sursa (job #2925930) | Cod sursa (job #2122951) | Cod sursa (job #842902) | Cod sursa (job #2925806)
/*
Algoritmul lui Tarjan
Din fiecare nod nevizitat inca se face un dfs
-marcam index de nod(id-ul) si lowLink(cel mai mic id la care se pate ajunge prin subarborele nodului) ca fiind nextIndex
-nextIndex creste
-punem nodul pe coada
-pentru toti vecinii lui nod daca unul nu e vizitat atunci se face dfs din nodul respectiv si dupa lowLink[nodul curent] e
minimul dintre valuarea sa si lowLink[vecin]
-altfel daca vecinul nu e pe coada muchia e intre doua componente conexe diferite
-altfel lowLink de nod e min(lowLink[nod], index[vecin])
Daca dupa ce se trec prin toti vecinii lowLink[nod] = index[nod] nod e radacina unui ctc si se elimina de pe stack toate nodurile care apartin acetui ctc
Alfel nu e radacina unui ctc si trebuie sa ramana pe stack
Complexitate O(N + M)
*/
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> edges[100001], cTC[100001];
stack<int> st;
class Solution {
int n, nextIndex = 1, index[100001], lowLink[100001], numberCTC;
bool onStack[100001];
public:
void run() {
read();
solve();
scrie();
}
void read() {
int m;
f >> n >> m;
while(m--) {
int x, y;
f >> x >> y;
edges[x].push_back(y);
}
f.close();
}
void solve() {
for(int i = 1; i <= n; ++i) {
if(!index[i]) {
dfs(i);
}
}
}
void dfs(int node) {
index[node] = nextIndex;
lowLink[node] = nextIndex;
nextIndex++;
onStack[node] = true;
st.push(node);
for(auto it : edges[node]) {
if(index[it] == 0) {
dfs(it);
lowLink[node] = min(lowLink[node], lowLink[it]);
} else if(onStack[it]) {
lowLink[node] = min(lowLink[node], index[it]);
}
}
if(index[node] == lowLink[node]) {
numberCTC++;
int x;
do {
x = st.top();
cTC[numberCTC].push_back(x);
st.pop();
lowLink[x] = index[node];
onStack[x] = false;
} while(x != node);
}
}
scrie() {
g << numberCTC << '\n';
for(int i = 1; i <= numberCTC; ++i) {
for(auto it : cTC[i]) {
g << it << " ";
}
g << '\n';
}
g.close();
}
};
int main()
{
Solution solution;
solution.run();
return 0;
}