Pagini recente » Cod sursa (job #2926922) | Cod sursa (job #606193) | Cod sursa (job #2396797) | Cod sursa (job #505142) | Cod sursa (job #3268955)
#include <bits/stdc++.h>
#define NMAX 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> rez;
vector<int> e[NMAX + 5];
vector<int> st;
int num[NMAX + 5], low[NMAX + 5], on_st[NMAX + 5], cnt;
void tarjan(int node)
{
low[node] = cnt;
num[node] = cnt;
cnt++;
st.push_back(node);
on_st[node] = 1;
for(auto adj : e[node])
{
if(num[adj] == 0)
tarjan(adj);
if(on_st[adj])
low[node] = min(low[node],low[adj]);
}
if(low[node] == num[node])
{
vector<int> rasp;
while(true)
{
int nod = st.back();
st.pop_back();
on_st[nod] = 0;
rasp.push_back(nod);
if(node == nod) break;
}
rez.push_back(rasp);
}
}
int main()
{
int n,m;
fin >> n >> m;
for(int i = 1; i<= m; i++)
{
int x, y;
fin >> x >> y;
e[x].push_back(y);
}
for(int i = 1; i<=n; i++)
{
if(num[i] == 0)
tarjan(i);
}
fout << rez.size() << '\n';
for(auto v : rez)
{
for(auto i : v)
fout << i << ' ';
fout << '\n';
}
return 0;
}