When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

VerbalKint's blog

By VerbalKint, history, 5 years ago, In English

I was solving this problem: https://www.spoj.com/problems/BREAK/ I figured that for a DAG, we can solve it by using indegree vector and simple dfs. Going though some online editorials, I noticed that there was mention of Strongly Connected Components. Can anyone tell me the intuition behind using SCC in this question. Any help is appreciated. Thanks

  • Vote: I like it
  • -2
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, in SCC we can reach any node to another. So, if the graph is SCC then answer is obviously $$$N$$$ for each number. Moreover, you can make a DAG with considering this SCC's as a vertex. You know how to solve it for DAG, so you only need to apply there and make correct calculations.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea behind SCCs is, that you can create a DAG from any arbitrary graph by contracting each SCC into a single node. The resulting graph is called "condensation graph", and is guaranteed to be a DAG. This is also fine, since the number of nodes every node in a SCC can reach is equal.

Why does having a DAG helps? Quite a bunch of problems can be solved efficiently on DAGs using DP. E.g. most of the game theory problems are based on that. However you can't apply DP on that problem. A first idea would be the recursion $$$f(v) = 1 + \sum_{(v, u) \in E} f(u)$$$, where $$$f(v)$$$ counts the number of reachable vertices from $$$v$$$. However it doesn't work because you double count vertices. E.g. look at the following graph and compute $$$f(1)$$$:

1->2
|  |
v  v
3->4

So even if you have a DAG, you need to do the trivial approach by running a DFS from each nodes, resulting in a runtime of $$$O(n m)$$$. And you can do that also on the normal graph in the same time complexity.

So does SCC help at all? Yes, because the test cases are not very good. I just tried to submit a solution without SCC, and it TLEd. And a solution with SCC got AC. On a random graph the condensation graph is usually a lot smaller than the original graph, which gives a decent performance boost (you only need to do one DFS for each SCC, instead one for each node, have less nodes and edges in general, ...). However it is possible to create graphs with $$$\Theta(n^2)$$$ edges, which correspond to their condensation graphs. In such a case you have a big graph, and computing the SCCs and the condensation graph will do nothing at all.

Note: it is possible to compute the answer faster than $$$O(n m)$$$. One method is to compute the transitive closure of the graph using matrix exponentiation. You can see in $$$A^n$$$ which vertex is reachable from which one, where $$$A$$$ is the adjacency matrix. Using binary exponantiation you can copmute $$$A^n$$$ in $$$O(n^3 \log n)$$$ time. If you use a faster matrix multiplication algorithm you can reduce the $$$n^3$$$ factor, and this pdf describes a way of getting rid of the logarithmic factor by first computing the condensation graph. However I doubt that such an approach can get the problem accepted.

»
4 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it
#include <bits/stdc++.h>
using  namespace std;

#define endl '\n'
#define ll long long
#define rint register int
#define minpq priority_queue <int, vector<int>, greater<int> >
#define maxpq  priority_queue <int>

#define re register
#define pb(x) push_back(x);
#define ce(x) cout << x << '\n';

using db = long double;
using pll = pair < ll, ll >;
#define scan(a, n) 		for(int i = 0; i < n; i++)cin >> a[i];

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 100007


#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (ll _tt = 0; _tt < tt; _tt++) // testcase 


vector<bool> used;
vector<ll> order, component, g[hell], gr[hell];
vector<vector<ll> > components;

void dfs1 (int v) {
	used[v] = true;
	for (size_t i = 0; i < g[v].size(); ++i)
		if (!used[ g[v][i] ])
			dfs1 (g[v][i]);
	order.push_back (v);
}

void dfs2 (int v) {
	used[v] = true;
	component.push_back (v);
	for (size_t i = 0; i < gr[v].size(); ++i)
		if (!used[ gr[v][i] ])
			dfs2 (gr[v][i]);
}

int32_t main() {
	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll t, i, x, j, y, m, 	z, k, n;
	tc(tt) {
		cin >> n >> m;
		ll c[n], ans[n];

		rep(i, 0, n, 1) {
			gr[i].clear();
			g[i].clear();
			c[i] = 1;
			ans[i] = 0;
		}
		order.clear();
		component.clear();
		while (components.size())	components.pop_back();
		map<ll, ll> ma;

		rep(i, 0, m, 1) {
			ll a, b;
			cin >> a >> b;	a--, b--;
			gr[a].push_back(b);
			g[b].push_back(a);
		}

		used.assign (n, false);
		for (int i = 0; i < n; ++i)
			if (!used[i])
				dfs1 (i);
		used.assign (n, false);


		for (ll i = 0; i < n; ++i) {
			int v = order[n - 1 - i];
			if (!used[v]) {
				dfs2 (v);
				ll z = 0, sz = components.size();

				for (auto zx : component)	{
					ma[zx] = sz;
					z += c[zx];
				}
				components.push_back(component);
				component.clear();
			}
		}

		int nscc = components.size();
		vector<int> isccs(n);
		for (int i = 0; i < nscc; i++) {
			for (auto u : components[i]) {
				isccs[u] = i;
			}
		}

		set<ll> s[nscc], rev[nscc], org[nscc];	bool used[nscc];

		for (int i = 0; i < nscc; i++)  {
			auto comp = components[i];
			used[i] = false;
			for (auto zx : comp) {
				for (auto v : g[zx]) {
					if (isccs[v] != i) {
						s[i].insert(isccs[v]);
						org[i].insert(isccs[v]);
					}
				}
				for (auto v : gr[zx]) {
					if (isccs[v] != i) {
						rev[i].insert(isccs[v]);
					}
				}
			}
		}

		std::deque<vector<ll> > ind;

		for (int i = 0; i < nscc; i++) {
			if (s[i].size() == 0) {
				ind.push_back(components[i]);
			}
		}

		while (ind.size()) {
			auto comp = ind.front();
			ind.pop_front();
			ll z = 0, idx = isccs[comp[0]];
			used[idx] = 1;

			for (auto zx : org[idx]) {
				z = max(z, ans[components[zx][0]]);
			}
			for (auto zx : rev[idx]) {
				if (!used[zx] && s[zx].count(idx)) {
					s[zx].erase(idx);
					if (s[zx].size() == 0) {
						ind.push_back(components[zx]);
					}
				}
			}

			for (auto zx : comp)	z += c[zx];
			for (auto zx : comp) {
				ans[zx] = z;
			}
		}

		ll z = *max_element(ans, ans + n);
		std::vector<ll> out;
		rep(i, 0, n, 1)	{
			if ( ans[i] == z) {
				out.push_back(1 + i);
			}
		}

		sort(all(out));
		for (auto zx : out)	cout << zx << " ";
		ce("")
	}
}

I made a code for it, passes most of the cases but don't know why it gives WA . Please if someone could help me out please help