Pagini recente » Cod sursa (job #3160677) | Cod sursa (job #539581) | Cod sursa (job #2657133) | Cod sursa (job #2515202) | Cod sursa (job #2923655)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
/*******************************/
// INPUT / OUTPUT
ifstream f("ctc.in");
ofstream g("ctc.out");
/*******************************/
/// GLOBAL DECLARATIONS
int N, M;
int id;
int ids[NMAX], low[NMAX];
bool in_stack[NMAX];
stack <int> s;
vector <int> adj[NMAX];
vector <vector < int > > ctc;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
f >> N >> M;
int a, b;
for (int i = 1 ; i <= M ; ++ i)
{
f >> a >> b;
adj[a].push_back(b);
}
}
///-------------------------------------
void dfs(int node)
{
ids[node] = low[node] = ++id;
in_stack[node] = true;
s.push(node);
for (auto u: adj[node])
{
if (!ids[u]) dfs(u);
if (in_stack[u]) low[node] = min(low[node], low[u]);
}
if (low[node] == ids[node])
{
int top;
vector <int> v;
do {
top = s.top();
s.pop();
in_stack[top] = false;
v.push_back(top);
} while (top != node);
ctc.push_back(v);
}
}
///-------------------------------------
inline void Solution()
{
for (int i = 1 ; i <= N ; ++ i)
{
if (!ids[i]) dfs(i);
}
}
///-------------------------------------
inline void Output()
{
g << ctc.size() << "\n";
for (auto v: ctc)
{
for (auto x: v)
g << x << " ";
g << "\n";
}
}
///-------------------------------------
int main()
{
ReadInput();
Solution();
Output();
return 0;
}