Pagini recente » Cod sursa (job #3227223) | Cod sursa (job #1673921) | Cod sursa (job #566344) | Cod sursa (job #1041933) | Cod sursa (job #1929284)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int NMAX = 100005;
vector <int> G[NMAX];
vector <int> CTC[100000];
int label[NMAX], lowlink[NMAX], index, nr, nodes, edges;
bool in_stack[NMAX];
stack <int> S;
void StrongCon (int node) {
int w;
label[node] = index;
lowlink[node] = index;
++ index;
S.push(node);
in_stack[node] = true;
for (auto &it: G[node]) {
if (label[it] == -1) {
StrongCon (it);
lowlink[node] = min (lowlink[node], lowlink[it]);
}
else if (in_stack[it]) {
lowlink[node] = min (lowlink[node], lowlink[it]);
}
}
if (lowlink[node] == label[node]) {
++ nr;
do
{
w = S.top ();
S.pop ();
in_stack[w] = false;
CTC[nr].push_back(w);
}while (node != w);
}
}
int main()
{
in >> nodes >> edges;
for (int i = 1; i <= edges; ++ i) {
int from, to;
in >> from >> to;
G[from].push_back(to);
}
for (int i = 1; i <= nodes; ++ i) {
label[i] = -1;
}
for (int i = 1; i <= nodes; ++ i) {
if (label[i] == -1) {
StrongCon (i);
}
}
out << nr << '\n';
for (int i = 1; i <= nr; ++ i) {
for (auto &it: CTC[i]) {
out << it << " ";
}
out << '\n';
}
return 0;
}