Pagini recente » Cod sursa (job #2131965) | Cod sursa (job #1363461) | Cod sursa (job #2627180) | Cod sursa (job #3125309) | Cod sursa (job #2566399)
#include <bits/stdc++.h>
#define MAXN 100005
#define FILENAME std::string("ctc")
int N, M;
std::vector <int> ADC[MAXN];
inline void addEdge(int u, int v) {
ADC[u].push_back(v);
}
int nctc;
int low[MAXN], disc[MAXN], _time;
std::vector <int> ctc[MAXN];
bool inStack[MAXN];
std::stack <int> stack;
void DFS(int vertex) {
disc[vertex] = low[vertex] = ++_time;
inStack[vertex] = true;
stack.push(vertex);
for (auto &it:ADC[vertex]) {
if (!disc[it]) {
DFS(it);
low[vertex] = std::min(low[vertex], low[it]);
}
else if (inStack[vertex]) {
low[vertex] = std::min(low[vertex], low[it]);
}
}
if (low[vertex] == disc[vertex]) {
while (!stack.empty() && stack.top() != vertex) {
ctc[nctc].push_back(stack.top());
inStack[stack.top()] = false;
stack.pop();
}
ctc[nctc].push_back(stack.top());
inStack[stack.top()] = false;
stack.pop();
++ nctc;
}
}
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");
int main()
{
input >> N >> M;
for (int i=1, u, v; i<=M; ++i) input >> u >> v, addEdge(u, v);
for (int i=1; i<=N; ++i)
if (!disc[i]) DFS(i);
output << nctc << '\n';
for (int i=0; i<nctc; ++i, output << '\n')
for (auto &it:ctc[i])
output << it << ' ';
return 0;
}