Cod sursa(job #2029425)

Utilizator vladm98Munteanu Vlad vladm98 Data 30 septembrie 2017 00:44:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.61 kb
#include <bits/stdc++.h>

using namespace std;
 
vector <int> graf[100005];
vector <int> igraf[100005];
vector <int> ctc[100005];
vector <int> compgraf[100005];
int in[100005];
int where[100005];
map <pair<int, int>, int> dist;
int cate;
int viz[100005];
queue <int> Q;
vector <int> v;
void bkt (int node, int lvl, int C, int start)
{
	if (dist.count({start, node}) == 0)
	{
		dist[{start, node}] = lvl;
	}
	else
	{
		int maxim = max(dist[{start, node}], lvl);
		dist[{start, node}] = maxim;
	}
	for (auto x:graf[node])
	{
		if (where[x] != where[node]) continue;
		if (viz[x]) continue;
		viz[x] = 1;
		bkt (x, lvl+1, C, start);
		viz[x] = 0;
	}
}
int dp[100005];
int dp_vechi[100005];
void dfs1 (int node)
{
	viz[node] = 1;
	for (auto x:graf[node])
	{
		if (viz[node]) continue;
		dfs1(x);
	}
	v.push_back(node);
}
void dfs2 (int node, int C)
{
	viz[node] = 0;
	where[node] = C;
	ctc[C].push_back(node);
	for (auto x:graf[node])
	{
		if (!viz[x]) continue;
		dfs2(x, C);
	}
}
int main(){
	freopen ("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i<=m; ++i)
    {
    	int x, y;
    	cin >> x >> y;
    	graf[x].push_back(y);
    	igraf[y].push_back(x);
    }
    for (int i = 1; i<=n; ++i)
    {
    	if (viz[i] == 0)
    		dfs1(i);
    }
    reverse(v.begin(), v.end());
    for (auto x:v)
    {
    	if (viz[x])
    	{
    		++cate;
    		dfs2(x, cate);
    	}
    }
    cout << cate << '\n';
    for (int i = 1; i<=cate; ++i)
    {
    	for (auto x:ctc[i])
    		cout << x << ' ';
    	cout << '\n';
    }
    return 0;
    for (int i = 1; i<=cate; ++i)
    {
    	// assert (ctc[i].size() <= 7);
    	for (auto j:ctc[i])
    	{
    		viz[j] = 1;
    		bkt(j, 0, i, j);
    		viz[j] = 0;
    	}
    }
    for (int i = 1; i<=n; ++i)
    {
    	int wi = where[i];
    	for (auto x:graf[i])
    	{
    		int wx = where[x];
    		if (wx == wi) continue;
    		in[wx]++;
    	}
    }
    for (int i = 1; i<=cate; ++i)
    {
    	if (in[i] == 0)
    	{
    		Q.push(i);
    	}
    }
    while (Q.empty() == 0)
    {
    	int CC = Q.front();
    	Q.pop();
    	for (auto x:ctc[CC])
    		dp_vechi[x] = dp[x];
    	for (auto x:ctc[CC])
    	{
    		for (auto y:ctc[CC])
    		{
    			dp[y] = max(dp_vechi[x] + dist[{x, y}], dp[y]);
    		}
    	}
    	for (auto x:ctc[CC])
    	{
    		for (auto y:graf[x])
    		{
    			if (where[y] == CC) continue;
    			dp[y] = max(dp[y], dp[x]+1);
    			in[where[y]]--;
    			if (in[where[y]] == 0) Q.push(where[y]);
    		}
    	}
    }
    int maxim = 0;
    for (int i = 1; i<=n; ++i)
    {
    	maxim = max(maxim, dp[i]);
    }
    cout << maxim+1;
    return 0;
}