Pagini recente » Rating Camelia Moise (adanu21) | Cod sursa (job #1299626) | Cod sursa (job #1655977) | Cod sursa (job #3129151) | Cod sursa (job #3215530)
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<unordered_map>
#include<map>
#include<unordered_set>
#include<ctime>
#include<random>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ld = long double;
mt19937 rng(time(nullptr));
constexpr int NMAX = 1e5 + 1;
vector<int> g[2][NMAX]; bool viz[NMAX];
void dfs(int v, int id, vector<int> &u)
{
viz[v] = 1; u.eb(v);
for(auto &it : g[id][v])
{
if(!viz[it])
dfs(it,id,u);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m,a,b; cin >> n >> m;
for(int i = 0 ; i < m ; i++)
{
cin >> a >> b;
g[0][a].eb(b);
g[1][b].eb(a);
}
vector<int> o;
for(int i = 1; i <= n ; i++)
if(!viz[i]) dfs(i,0,o);
reverse(o.begin(),o.end()); memset(viz,0,sizeof(viz));
vector<vector<int>> comps;
for(auto &v : o)
{
if(viz[v]) continue;
vector<int> comp; dfs(v,1,comp);
comps.pb(comp);
}
cout << comps.size() << '\n';
for(int i = 0 ; i < comps.size() ; i++, cout << '\n')
{
sort(comps[i].begin(),comps[i].end());
for(auto &it : comps[i])
cout << it << " ";
}
}