Pagini recente » Cod sursa (job #2307720) | Cod sursa (job #54691) | Cod sursa (job #342413) | Cod sursa (job #1315661) | Cod sursa (job #3168771)
#include <bits/stdc++.h>
using namespace std;
///TOGGLES ---------------------------------------------
//#define INDEX_0
//#define int long long
//#define DEBUG
//#define LOCAL
//#define DEBUG_READ
#ifndef LOCAL
#define FIO
#endif // LOCAL
///DEFINES ---------------------------------------------
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define iter(x) x::iterator
#define z(x) (x&(-x))
#define fr first
#define se second
#define mp make_pair
#ifdef INDEX_0
#define forn(i,n) for(int i=0;i<n;i++)
#else
#define forn(i,n) for(int i=1;i<=n;i++)
#endif // INDEX_0
#define forit(i,n) for(auto i:n)
#define IOS ios::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0);
#ifdef FIO
const string name = "ctc";
ifstream in(name+".in");
ofstream out(name+".out");
#define cin in
#define cout out
#endif // FIO
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<vector<int>> vvi;
typedef vector<vector<pii>> vvp;
typedef const int cint;
typedef long long ll;
///CONSTANTS ---------------------------------------------
cint MN = 1e5+5;
cint MQ = 5e5+5;
cint M = 1e9+5;
cint MB = 31;
cint MV = (1<<MB);
///GLOBALS ---------------------------------------------
int n, m;
vector<int> adj[MN];
int inStack[MN], stackPoz[MN], lowlink[MN];
bool vis[MN];
vector<int> stk;
vector<vector<int>> ctc;
///CODE ---------------------------------------------
void dfs(int nod)
{
vis[nod]=1;
inStack[nod]=1;
stackPoz[nod]=stk.size();
lowlink[nod]=stackPoz[nod];
stk.push_back(nod);
for(auto e:adj[nod])
{
if(inStack[e])
{
lowlink[nod]= min(lowlink[nod], stackPoz[e]);
}
else
{
dfs(e);
lowlink[nod]= min(lowlink[nod], lowlink[e]);
}
}
//cout<<"here "<<nod<<' '<<lowlink[nod]<<' '<<stackPoz[nod]<<'\n';
if(lowlink[nod]==stackPoz[nod])
{
//avem o componenta
ctc.push_back(vector<int>());
while(stk.back()!=nod)
{
ctc.back().push_back(stk.back());
//inStack[stk.back()]=0;
stk.pop_back();
}
ctc.back().push_back(stk.back());
inStack[nod]=0;
stk.pop_back();
}
}
#ifdef DEBUG_READ
void debugRead()
{
}
#endif // DEBUG_READ
void readInput()
{
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
adj[a].push_back(b);
}
}
void solve()
{
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs(i);
}
}
cout<<ctc.size()<<'\n';
for(auto comp:ctc)
{
for(auto e:comp)
{
cout<<e<<' ';
}
cout<<'\n';
}
}
int32_t main()
{
IOS;
int t = 1;
//cin >> t;
#ifdef LOCAL
cout<<"running locally!\n"<<'\n';
#endif // LOCAL
while (t--)
{
#ifdef DEBUG_READ
debugRead();
#else
readInput();
#endif // DEBUG_READ
solve();
}
}
/*
8 12
1 2
2 6
6 7
7 6
3 1
3 4
2 3
4 5
5 4
6 5
5 8
8 7
*/