Pagini recente » Cod sursa (job #2558130) | Cod sursa (job #2228953) | Cod sursa (job #2091548) | Cod sursa (job #440625) | Cod sursa (job #3168776)
#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], order[MN], lowlink[MN];
int ordk=0;
bool vis[MN];
vector<int> stk;
vector<vector<int>> ctc;
///CODE ---------------------------------------------
void dfs(int nod)
{
vis[nod]=1;
inStack[nod]=1;
lowlink[nod]=order[nod]=++ordk;
stk.push_back(nod);
//cout<<"entering "<<nod<<' '<<lowlink[nod]<<' '<<order[nod]<<'\n';
for(auto e:adj[nod])
{
if(inStack[e])
{
lowlink[nod]= min(lowlink[nod], order[e]);
}
else if(!vis[e])
{
dfs(e);
lowlink[nod]= min(lowlink[nod], lowlink[e]);
}
}
//cout<<"leaving "<<nod<<' '<<lowlink[nod]<<' '<<order[nod]<<'\n';
if(lowlink[nod]==order[nod])
{
//avem o componenta
ctc.push_back(vector<int>());
int nxt=0;
do
{
nxt=stk.back();
stk.pop_back();
ctc.back().push_back(nxt);
inStack[nxt]=0;
} while(nxt!=nod);
}
}
#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
*/