Pagini recente » Cod sursa (job #1896717) | Cod sursa (job #2828479) | Cod sursa (job #2689430) | Cod sursa (job #1935206) | Cod sursa (job #2886831)
#include <fstream>
#include <stack>
#include <vector>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int const NMAX = 1e5;
std::vector<int> G[NMAX + 5];
int currindex = 0;
int index[NMAX + 5];
int low[NMAX + 5];
bool onStack[NMAX + 5];
std::vector <std::vector <int>> scc;
int sccCount = 0;
std::stack<int> st;
void dfs(int node) {
index[node] = ++currindex;
low[node] = index[node];
st.push(node);
onStack[node] = true;
for (auto x : G[node]) {
if (index[x] == 0) {
dfs(x);
low[node] = std::min(low[node], low[x]);
} else if (onStack[x])
low[node] = std::min(low[node], index[x]);
}
if (low[node] == index[node]) {
sccCount++, scc.push_back({});
while (!st.empty()) {
int x = st.top(); st.pop();
scc[sccCount - 1].push_back(x);
onStack[x] = false;
if (x == node)
break;
}
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
}
dfs (1);
fout << sccCount << "\n";
for (int i = 0; i < sccCount; i++) {
int size = scc[i].size();
for (int j = 0; j < size; j++)
fout << scc[i][j] << " ";
fout << "\n";
}
return 0;
}