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