Pagini recente » Borderou de evaluare (job #2012382) | Cod sursa (job #1532375) | Cod sursa (job #1724513) | Cod sursa (job #821780) | Cod sursa (job #2927090)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N_MAX = 1e5 + 5;
int N, M;
int onStack[N_MAX], index[N_MAX], lowlink[N_MAX], idx;
stack <int> S;
vector <int> G[N_MAX];
vector <vector <int>> Ans;
void strongConnect(int currNode) {
index[currNode] = idx;
lowlink[currNode] = idx;
idx++;
S.push(currNode);
onStack[currNode] = 1;
for (int node : G[currNode]) {
if (index[node] == 0) {
strongConnect(node);
lowlink[currNode] = min(lowlink[currNode], lowlink[node]);
}
else if (onStack[node]) {
lowlink[currNode] = min(lowlink[currNode], index[node]);
}
}
if (index[currNode] == lowlink[currNode]) {
vector <int> scc;
while (!S.empty()) {
int node = S.top();
S.pop();
onStack[node] = 0;
scc.push_back(node);
}
Ans.push_back(scc);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
fin >> N >> M;
for (int i = 1; i <= M; i++) {
int u, v;
fin >> u >> v;
G[v].push_back(u);
}
idx = 1;
for (int i = 1; i <= N; i++) {
if (index[i] == 0) {
strongConnect(i);
}
}
fout << Ans.size() << "\n";
for (int i = 0; i < Ans.size(); i++) {
for (int j = 0; j < Ans[i].size(); j++) {
fout << Ans[i][j] << " ";
}
fout << "\n";
}
return 0;
}