But, when I heard what kind of solution passed, I realized that the test data was bad, too.
Here is the test case:
Code: Select all
1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Moderator: Board moderators
Code: Select all
1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
jan_holmes wrote:I was using union-find algorithm at the contest. But I got several WA's. I think my program failed in handling reversible connection (i.e. 1->2 and 2->1).
Code: Select all
1
10 13
1 2
2 1
3 4
4 3
5 6
6 5
4 6
7 8
8 7
9 10
10 9
5 10
10 1
Anindya wrote:For the following input:
the output should be 2.Code: Select all
1 10 13 1 2 2 1 3 4 4 3 5 6 6 5 4 6 7 8 8 7 9 10 10 9 5 10 10 1
AC code outputs 3.
The input is taken from waterloo site.
Then how the case is not included in UVa?
The thing is I used C++ during the contest.Darko wrote:Maybe something to do with the note in your signature?I don't know how big Pascal stack is, but I got RTE when I tried DFS in Java.
When you traversed the connected components, did you consider the graph directed or not directed?Darko wrote: I went through all connected components and counted nodes with indegree 0. If there were none, I would add one. That timed out and it's linear in number of edges, so I gave up after trying to optimize it for a while.
Code: Select all
using namespace std;
#include <iostream>
#include <vector>
const int N = 100005;
vector<int> g[N];
int color[N];
enum { standing, tiled, handed };
void dfs(int u, int root){
if (color[u] != standing) return;
if (u == root) color[u] = handed;
else color[u] = tiled;
vector<int> &out = g[u];
for (int k=0, m=out.size(); k<m; ++k){
int v = out[k];
if (color[v] == handed && v != root) color[v] = tiled;
else if (color[v] == standing) dfs(v, root);
}
}
int main(){
int t;
for(cin >> t; t--;){
int n, m; cin >> n >> m;
for (int i=0; i<=n; ++i) g[i].clear(), color[i] = standing;
for (int u, v, i=0; i<m && cin >> u >> v; ++i) g[u].push_back(v);
for (int i=1; i<=n; ++i) if (color[i] == standing) dfs(i, i);
int ans = 0;
for (int i=1; i<=n; ++i) ans += (color[i] == handed);
cout << ans << endl;
}
return 0;
}
Code: Select all
1
4 4
1 2
2 3
3 1
4 2
That's because union-find is for undirected graphs and this is a directed graph here. For example a case like this:wahaha wrote:jan_holmes wrote:I was using union-find algorithm at the contest. But I got several WA's. I think my program failed in handling reversible connection (i.e. 1->2 and 2->1).
i use union-find algorithm , and i got WA too . i think this algorithm is correct , but why i got wrong ?
Code: Select all
1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Code: Select all
1
10 5
1 2
2 5
3 4
1 3
2 3