Pagini recente » Cod sursa (job #3293363) | Cod sursa (job #3287414) | Cod sursa (job #3290656) | Cod sursa (job #3293417) | Cod sursa (job #3287054)
//kosaraju:
//sortezi topologic
//iei de la coada sortarea si vezi daca ai muchie spre tine din alt nod
//daca ai ai gasit un ciclu => componenta conexa
//tarjan:
//la fel doar ca diferit
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 1e5;
vector<int> graph[NMAX + 1];
stack<int> s; //asta e cu nodurile care sunt mai sus ca mine, in ordine de la cel mai apropiat
//dar si cu alea de mai jos daca au muchie mai sus sau la mine
//i.e. toate care ma pot accesa
bool onstack[NMAX + 1];
int curr_idx = 1;
int idx[NMAX + 1], lowlink[NMAX + 1];
int no_components;
vector<int> components[NMAX + 1];
void dfs(int curr_node) {
idx[curr_node] = curr_idx;
lowlink[curr_node] = curr_idx;
curr_idx++;
s.push(curr_node);
onstack[curr_node] = true;
for (auto nxt : graph[curr_node]) {
if (!idx[nxt]) {
dfs(nxt);
lowlink[curr_node] = min(lowlink[curr_node], lowlink[nxt]);
}
else if (onstack[nxt]) {
lowlink[curr_node] = min(lowlink[curr_node], lowlink[nxt]);
}
}
if (lowlink[curr_node] == idx[curr_node]) { //aici mi se rupe componenta
no_components++;
int w;
do {
w = s.top();
s.pop();
onstack[w] = false;
components[no_components].push_back(w);
} while (w != curr_node);
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
for (int i = 1; i <= n; i++)
if (!idx[i])
dfs(i);
cout << no_components << '\n';
for (int i = 1; i <= no_components; i++, cout << '\n')
for (auto node : components[i])
cout << node << ' ';
}