Pagini recente » Cod sursa (job #1605541) | Cod sursa (job #1709198) | Cod sursa (job #3162952) | Cod sursa (job #1025404) | Cod sursa (job #2719717)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;
int m, n;
vector<int> G[NMAX];
vector<int>v;
vector<vector<int> >sol;
stack<int>st;
int ids[NMAX];
int lowlink[NMAX];
bool onStack[NMAX];
int id = 0;
void read()
{
fin >> n >> m;
while (m--)
{
int a, b;
fin >> a >> b;
G[a].push_back(b);
}
}
void init()
{
for (int i = 1; i <= n; i++)
ids[i] = -1;
}
void dfs(int u)
{
st.push(u);
ids[u] = lowlink[u] = ++id;
onStack[u] = true;
for (int v : G[u])
{
if (ids[v] == -1)
{
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if(onStack[v])
lowlink[u] = min(lowlink[u], lowlink[v]);
}
if (lowlink[u] == ids[u])
{
v.clear();
while (!st.empty())
{
int nod = st.top();
v.push_back(nod);
onStack[nod] = false;
lowlink[nod] = lowlink[u];
st.pop();
if (nod == u) break;
}
sort(v.begin(), v.end());
sol.push_back(v);
}
}
void solve()
{
for (int i = 1; i <= n; i++)
if (ids[i] == -1)
dfs(i);
fout << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++)
{
for (int e : sol[i])
fout << e << ' ';
fout << '\n';
}
}
int main()
{
read();
init();
solve();
return 0;
}