Question

ACM的一道简单题，向大牛们求助啊

这是一道并查集的题，大牛们帮帮我吧.
网址：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2223
原题是：
由于 超出字数限制 所以题目简写.
说的是一个教授研究虫子的交配，他想看看在一大群虫子中有没有同性恋者。。。。。
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
Input Specification
The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.
Output Specification
the output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.
以下是我的代码：
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int father[2001],rank[2001];
int find(int x)
{
if(father[x]==x)
return x;
else
return father[x]=find(father[x]);
}
void unin(int a,int b)
{
int x=find(a);
int y=find(b);
if(rank[x]>rank[y])
father[y]=x;
else if(rank[x]<rank[y])
father[x]=y;
else
{
rank[x]++;
father[y]=x;
}
}
int main()
{
int total_num,itor;
scanf("%d",&total_num);
for(itor=1;itor<=total_num;itor++)
{
int bug,inter;
scanf("%d%d",&bug,&inter);
int i;
for(i=1;i<=bug;i++)
father[i]=i,rank[i]=0;
vector<int> g[2001];
for(i=0;i<inter;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
int j;
for(i=1;i<=bug;i++)
{
for(j=1;j<g[i].size();j++)
if(find(g[i][0])!=find(g[i][j]))
unin(g[i][0],g[i][j]);
}
int flag=1;
for(i=1;i<=bug;i++)
{
for(j=0;j<g[i].size();j++)
if(find(i)==find(g[i][j]))
{
flag=0;
break;
}
if(!flag)
break;
}
if(flag==0)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",itor);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",itor);
}
}

错误是runtime error：stop single is 5
我弄了一上午 实在想不出哪错了 都快崩溃了 大牛们帮帮我吧
网址：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2223

Answer 1

这个是因为你的变量
int eenum[3020000];
int jnum[500000];
是定义在栈里的，而windows里面每个应用程序能使用的栈空间最大只有1MB，你这应经超过范围了，所以会出现栈溢出的错误，但是下面的代码是把这两个数组定义在全局范围的，所以没有你这个限制，因此没有错误，其实程序的逻辑上这两个程序没什么区别的，你只要把这两个定义为全局的就好了

追问

但我把向量定义成全局的还是runtime error，这是怎么回事啊。

Answer 2

直接BFS即可
不用并查集
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

bool adj[2001][2001];

bool odd[2001];
bool vis[2001];
bool sex[2001];
bool flag;
int num;
void bfs(int j)
{
queue<int> q;
while(!q.empty()) q.pop();
q.push(j);
odd[j] = true;
vis[j] = true;
int loc;
while(flag&&!q.empty())
{
loc = q.front();
q.pop();
for(int it=0;it<num;it++)
{
if(adj[loc][it]==false) continue;
if(vis[it])
{
if(odd[it] == odd[loc])
{
flag = false;
return;
}
}
else
{
vis[it] = true;
odd[it] = !(odd[loc]);
q.push(it);
}
}
}
}

int main()
{
int N;
cin >> N;
for(int i=1;i<=N;i++)
{
cout << "Scenario #" << i << ":" << endl;
cin >> num;
int inter;
cin >> inter;
flag = true;
memset(adj,0,sizeof(adj));
for(int j=0;j<inter;j++)
{
int m,n;
cin >> m >> n;
if(!flag) continue;
if(m<=num&&n<=num&&m>0&&n>0)
{
adj[m-1][n-1] = adj[n-1][m-1] = true;
}
else
flag = false;
}

memset(vis,0,sizeof(bool)*num);
for(int j=0;flag&&j<num;j++)
{
if(!vis[j])
bfs(j);
}
if(!flag)
cout << "Suspicious bugs found!" << endl << endl;
else cout << "No suspicious bugs found!" << endl << endl;
}
return 0;
}

追问

但是我还是不明白我哪里错了，能不能帮我看一下，谢谢啦，我是一个刚起步的新手

追答

说实话，我刚才也一直在尝试用vector。不知道为什么和你一样RE，我觉得应该不是程序有错，而是栈溢出了。
我换成接邻矩阵就过了

追问

把向量定义成全局的应该就不会溢出了，可是还是不行啊。

追答

具体我也不是特别清楚了。。。

Answer 3

好邪恶的孩子...

Answer 4

170035036 加这个群 问问里面的高手