MagicantPlus
Iuoras Andrei
• MagicantPlus
logout | contul meu
infoarena informatica de performanta

    infoarena
    blog
    forum
    calendar
    profilul meu
    mesaje

    Home
    Arhiva de probleme
    Arhiva educatională
    Arhiva monthly
    Arhiva ACM
    Concursuri
    Concursuri virtuale
    Clasament
    Articole
    Downloads
    Links
    Documentaţie
    Despre infoarena
    Monitorul de evaluare
    Trimite soluţii
    Contul meu

! Cautare
In curand...

168915 membri inregistrati
00:22:58

Fii un bun infoarenaut! Implică-te!

Pagini recente » Componente tare conexe | Monitorul de evaluare | Monitorul de evaluare | Borderou de evaluare (job #3269140) | Cod sursa (job #3269140)
Cod sursa(job #3269140)
Utilizator 	MagicantPlusIuoras Andrei MagicantPlus 	Data 	18 ianuarie 2025 11:32:25
Problema 	Componente tare conexe 	Scor 	100
Compilator 	cpp-64 	Status 	done
Runda 	Arhiva educationala 	Marime 	4.83 kb
Raporteaza aceasta sursa

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll
#define vec vector
#define flist forward_list
#define um unordered_map
#define us unordered_set
#define prioq priority_queue
#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ld long double
#define pll pair<ll, ll>
#define tll tuple<ll, ll, ll>
#define ass assign

#define LL_MAX LLONG_MAX
#define LL_MIN LLONG_MIN
#define ULL_MAX ULLONG_MAX
#define LD_MAX LDBL_MAX
#define LD_MIN LDBL_MIN

#define nl '\n'

#define vv(type, name, n, ...) vector<vector<type>> name(n, vector<type>(__VA_ARGS__))
#define vvv(type, name, n, m, ...)                                                                                     \
    vector<vector<vector<type>>> name(n, vector<vector<type>>(m, vector<type>(__VA_ARGS__)))

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rep1e(n) for(ll i=1; i<=(ll)(n); ++i)
#define rep2e(i,n) for(ll i=1; i<=(ll)(n); ++i)
#define rep3e(i,a,b) for(ll i=(ll)(a); i<=(ll)(b); ++i)
#define rep4e(i,a,b,c) for(ll i=(ll)(a); i<=(ll)(b); i+=(c))
#define repe(...) cut4(__VA_ARGS__,rep4e,rep3e,rep2e,rep1e)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define per1e(n) for(ll i=((ll)n); i>=1; --i)
#define per2e(i,n) for(ll i=((ll)n); i>=1; --i)
#define per3e(i,a,b) for(ll i=((ll)a); i>=(ll)(b); --i)
#define per4e(i,a,b,c) for(ll i=((ll)a); i>=(ll)(b); i-=(c))
#define pere(...) cut4(__VA_ARGS__,per4e,per3e,per2e,per1e)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
// #define forit(v) for (auto it = v.begin(); it != v.end(); it++)
// #define forit2(it, v) for (auto it = v.begin(); it != v.end(); it++)
// #define forrit(v) for (auto it = v.rbegin(); it != v.rend(); it++)
// #define forrit2(it, v) for (auto it = v.rbegin(); it != v.rend(); it++)

// #ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<vector<T>> x){cerr << "\n"; for(auto i: x) {for(auto j : i) {cerr << j << ' ';} cerr << "\n";}}
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
// #else
// #define bug(...) 777771449
// #endif

const ll MOD = 1e9 + 7;
const ll INF = (1ll << 59);

const string FILENAME = "ctc";
ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");

#define cin fin
#define cout fout

class Graph;
class Tarjan;
class Kosaraju;
class Topsort;

class Graph
{
public:

	ll n;
	vec<flist<ll>> adj;
	
	// Tarjan *tarjo;
	Kosaraju *koso;
	
	void read();
	void solve();
};

class Topsort
{
public:

	Graph *g;
	vec<ll> topsort;
	vec<bool> vis;
	
	void build(Graph *gc)
	{
		g = gc;
		topsort.reserve(g->n);
		vis.ass(g->n, 0);
		rep(g->n) if(!vis[i]) dfs(i);
	}
	void dfs(ll u)
	{
		vis[u] = 1;
		for(auto v : g->adj[u]) if(!vis[v]) dfs(v);
		topsort.pb(u);
	}
};
class Kosaraju
{
public:

	list<list<ll>> sccs;
	vec<flist<ll>> tadj;
	vec<bool> vis;
	Topsort *topso;
	Graph *g;
	
	void build(Graph *gc)
	{
		g = gc;
		topso = new Topsort;
		topso->build(g);
		
		tadj.resize(g->n);
		rep(g->n) for(auto& v : g->adj[i]) tadj[v].pf(i);
		
		vis.ass(g->n, 0);
		per(g->n)
		{
			ll node = topso->topsort[i];
			if(vis[node]) continue;
			vis[node] = 1;
			queue<ll> nn;
			nn.push(node);
			
			sccs.pb({});
			while(!nn.empty())
			{
				ll u = nn.front(); nn.pop();
				sccs.back().pb(u);
				
				for(auto v : tadj[u])
				{
					if(vis[v]) continue;
					vis[v] = 1;
					nn.push(v);
				}
			}
		}
	}
};


void Graph::solve()
{
	// tarjo = new Tarjan;
	// tarjo->build(this);
	koso = new Kosaraju;
	koso->build(this);
	
	// list<list<ll>> &sccs = tarjo->sccs;
	list<list<ll>> &sccs = koso->sccs;
	
	cout << sccs.size() << nl;
	
	for(auto& scc : sccs)
	{
		for(auto& e : scc)
		{
			cout << e+1 << ' ';
		}
		cout << nl;
	}
}
void Graph::read()
{
	ll m;
	cin >> n >> m;
	adj.resize(n);
	rep(m)
	{
		ll a, b;
		cin >> a >> b;
		a--, b--;
		adj[a].pf(b);
	}
}

int main()
{
	Graph g;
	g.read();
	g.solve();
	
    return 0;
}