Pagini recente » Cod sursa (job #2646896) | Cod sursa (job #647653) | Cod sursa (job #2112877) | Cod sursa (job #1650760) | Cod sursa (job #2804101)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<map>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<vector>
#include<stack>
#include<queue>
#include<limits>
#define all(v) v.begin(),v.end()
#define sorti(v) sort(all(v))
#define desc(x) greater<x>()
#define lsb(x) ((x)&(-x))
#define sortd(v) sort(all(v),desc(decltype(v[0])))
#define hmap unordered_map
#define var auto&
#define hset unordered_set
#define pq priority_queue
#define inf 0x3f3f3f3f
#define exists(x,v) (v.find(x)!=v.end())
#define inrange(x,a,b) (x>=a && x<=b)
#define printv(v) {for(auto it:v) cout<<it<<' ';cout<<'\n';}
#define printa(v,a,b) {for(int i=a;i<=b;i++ ) cout<<v[i]<<' ';cout<<'\n';}
#define MOD 66
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
template<typename T> T gcd(T a, T b) { T c; while (b) { c = a % b; a = b; b = c; }return a; }
template<typename T> T exp(T a, T n, T m) { T p = 1; while (n) { if (n & 1)p = (p % m * a % m) % m; a = (a % m * a % m) % m; n >>= 1; }return p; }
template<typename T> T exp(T a, T n){T p = 1; while (n) { if (n & 1)p *= a; a *= a; n >>= 1; }return p;}
template<typename T> T invm(T a, T m) {return exp(a, m - 2, m);}
const int lim = 1e5 + 6;
vector<int> g[lim];
vector<int> disc,low;
int idx;
bool inStack[lim];
stack<int> s;
vector<vector<int>>sol;
int n, m;
void tarjan(int nod)
{
disc[nod] = low[nod] = ++idx;
s.push(nod);
inStack[nod] = true;
for (auto it : g[nod])
if (disc[it] == -1)
{
tarjan(it);
low[nod] = min(low[nod], low[it]);
}
else
if (inStack[it])
low[nod] = min(low[nod], low[it]);
if (low[nod] == disc[nod])
{
int head;
vector<int> scc;
do
{
scc.push_back(head = s.top());
s.pop();
inStack[head] = false;
} while (head != nod);
sol.push_back(scc);
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
}
disc.resize(n + 1, -1);
low.resize(n + 1, -1);
for (int i = 1; i <= n; i++)
if (disc[i]==-1)
tarjan(i);
cout << sol.size()<<'\n';
for (var it : sol)
{
for (var ij : it)
cout << ij << " ";
cout << '\n';
}
}