Pagini recente » Cod sursa (job #2276276) | Cod sursa (job #919320) | Cod sursa (job #1227939) | Cod sursa (job #1079257) | Cod sursa (job #2664908)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<int>> adiacenta(100001);
int ids[100001], low[100001];
bool onStack[100001] = {false};
stack<int> stck;
int n, m, sccCount = 0, id = 0;
vector<vector<int>> rez;
void dfs(int node) {
stck.push(node);
onStack[node] = true;
ids[node] = low[node] = id++;
for(int x : adiacenta[node]) {
if(ids[x] == -1) {
dfs(x);
low[node] = min(low[node], low[x]);
}
else if(onStack[x])
low[node] = min(low[node], ids[x]);
}
if(ids[node] == low[node]) {
vector<int> v_aux;
cout << endl;
int aux;
while(stck.top() != node) {
aux = stck.top();
stck.pop();
//cout << aux << endl;
onStack[aux] = false;
v_aux.push_back(aux);
}
aux = stck.top();
v_aux.push_back(aux);
stck.pop();
sccCount++;
rez.push_back(v_aux);
}
}
void findSccs() {
for(int i = 1; i <= n; i++) {
ids[i] = -1;
}
for(int i = 1; i <= n; i++)
if(ids[i] == -1)
dfs(i);
}
int main() {
int x, y;
f >> n >> m;
for(int i = 0; i < m; i++) {
f >> x >> y;
adiacenta[x].push_back(y);
}
findSccs();
g << sccCount << endl;
for(int i = 0; i < rez.size(); i++) {
for (int j = 0; j < rez[i].size(); j++)
g << rez[i][j] << " ";
g << endl;
}
return 0;
}