/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 bool vis[MX]; vector<int>adj[MX], topSort; void dfs(int u) { vis[u]=true; for(int i=0; i<adj[u].size(); i++) { int v=adj[u][i]; if(!vis[v]) dfs(v); } topSort.push_back(u); return; } int connectedComponent(int n) { CLR(vis); for(int i=1; i<=n; i++) if(!vis[i]) dfs(i); CLR(vis); int cnt=0; for(int i=topSort.size()-1; i>=0; i--) //as topSort contains the reverse of topological order if(!vis[topSort[i]]) { cnt++; dfs(topSort[i]); } return cnt; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc, kk=1, n, m, u, v; cin>>tc; while(tc--) { cin>>n>>m; for(int i=0; i<m; i++) { cin>>u>>v; adj[u].push_back(v); } cout<<connectedComponent(n)<<"\n"; topSort.clear(); for(int i=1; i<=n; i++) adj[i].clear(); } return 0; }
Thursday, 10 May 2012
UVa 11504 Dominos Solution (HDU - 3173, NBUT - 1247)
Subscribe to:
Post Comments (Atom)
Why did you make two DFS?
ReplyDelete1st DFS for Topological Sort. 2nd one to get minimum cnt. if you don't Sort first, you may not get the minimum.
DeleteIf you want more information about this algorithm it is Kosaraju's algorithm.
Deletewhy will I not get the minimum without using top sort?
DeleteHi Raihan,
ReplyDeleteNice solution. But can you explain as to why second DFS is needed? Can't we just count the number of distinct components while doing first DFS? Shouldn't that also be the answer? Please let me know if I am missing here something.
Thanks
you have to find number of connected component. only 1 dfs would be enough if the graph was bi-directional.
DeleteI think I know the reason. Basically say it took 3 DFS to visit the entire graph if you started in sequential manner (starting from 1...... n). Now obviously it may be possible to visit the same graph in less number of DFS. And that's what we need to find out? Is that correct? So bascially this question is asking - find minimum number of DFS that you need to run to visit every node in the graph? Am I thinking right?
ReplyDelete