2015
02-22

# Financial Crisis

Because of the financial crisis, a large number of enterprises go bankrupt. In addition to this, other enterprises, which have trade relation with the bankrup enterprises, are also faced with closing down. Owing to the market collapse, profit decline and funding chain intense, the debt-ridden entrepreneurs
have to turn to the enterprise with stably developing for help.

The Input consists of multiple test cases. The first line of each test case contains three integers, N ( 3 <= N <= 5000 ), M ( 0 <= M <= 10000 ) and Q ( 1 <= Q <= 1000 ). which are the number of enterprises, the number of the financial trade relations and the number of queries.
The next M lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means enterpirse u and enterprise v have trade relations, you can assume that the input will not has parallel edge.
The next Q lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means entrepreneurs will ask you the financial safety of enterpirse u and enterprise v.
The last test case is followed by three zeros on a single line, which means the end of the input.

The Input consists of multiple test cases. The first line of each test case contains three integers, N ( 3 <= N <= 5000 ), M ( 0 <= M <= 10000 ) and Q ( 1 <= Q <= 1000 ). which are the number of enterprises, the number of the financial trade relations and the number of queries.
The next M lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means enterpirse u and enterprise v have trade relations, you can assume that the input will not has parallel edge.
The next Q lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means entrepreneurs will ask you the financial safety of enterpirse u and enterprise v.
The last test case is followed by three zeros on a single line, which means the end of the input.

3 1 2
0 1
0 2
1 0
4 4 2
0 1
0 2
1 2
2 3
1 2
1 3
0 0 0

Case 1:
zero
one
Case 2:
two or more
one

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 111111
#define MAXM 211111
#define eps 1e-8
#define INF 1000000001
using namespace std;
int e, tmpdfn, top;
int n, m, ind;
int vis[MAXM], head[MAXN], dfn[MAXN], low[MAXN], num[MAXM];
vector<int>g[MAXN];
struct Edge
{
int v, next;
}edge[MAXM];
{
edge[e].v = v;
edge[e].v = u;
}
struct Stack
{
int s, e;
Stack(){}
Stack(int a, int b){s = a; e = b;}
}st[MAXM];
void init()
{
e = tmpdfn = ind = 0;
top = -1;
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
memset(num, 0, sizeof(num));
}
void color(Stack t)
{
ind++;
while(top >= 0)
{
Stack A = st[top--];
g[A.s].push_back(ind);
g[A.e].push_back(ind);
if(A.s == t.s && A.e == t.e) break;
}
}
void dfs(int u, int fa)
{
dfn[u] = low[u] = ++tmpdfn;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(vis[i] == 0)
{
vis[i] = vis[i ^ 1] = 1;
Stack tmp(u, v);
st[++top] = tmp;
if(!dfn[v])
{
dfs(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) color(tmp);
}
else if(v != fa) low[u] = min(low[u], dfn[v]);
}
}
}
int Q;
int uu[MAXM], vv[MAXM];
int fa[MAXN];
int find(int x)
{
if(fa[x] == x) return x;
int t = find(fa[x]);
fa[x] = t;
return t;
}
void join(int u, int v)
{
int fx = find(u);
int fy = find(v);
if(fx != fy) fa[fx] = fy;
}
int main()
{
int u, v;
int cas = 0;
while(scanf("%d%d%d", &n, &m, &Q) != EOF)
{
if(n == 0 && m == 0 && Q == 0) break;
init();
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 0; i < m; i++)
{
scanf("%d%d", &uu[i], &vv[i]);
uu[i]++; vv[i]++;
join(uu[i], vv[i]);
}
for(int i = 1; i <= n; i++) g[i].clear();
for(int i = 1; i <= n; i++)
{
if(!dfn[i]) dfs(i, 0);
}
for(int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
for(int i = 1; i <= n; i++) unique(g[i].begin(), g[i].end());

for(int i = 0; i < m; i++)
{
int sz1 = g[uu[i]].size();
int sz2 = g[vv[i]].size();
int k1 = 0, k2 = 0;
while(k1 < sz1 && k2 < sz2)
{
if(g[uu[i]][k1] > g[vv[i]][k2]) k2++;
else if(g[uu[i]][k1] < g[vv[i]][k2]) k1++;
else if(g[uu[i]][k1] == g[vv[i]][k2])
{
int tmp = g[uu[i]][k1];
num[tmp]++;
break;
}
}
}
printf("Case %d:\n", ++cas);
for(int i = 0; i < Q; i++)
{
scanf("%d%d", &u, &v);
u++; v++;
int sz1 = g[u].size();
int sz2 = g[v].size();
int k1 = 0, k2 = 0;
int tmp = -1;
while(k1 < sz1 && k2 < sz2)
{
if(g[u][k1] > g[v][k2]) k2++;
else if(g[u][k1] < g[v][k2]) k1++;
else if(g[u][k1] == g[v][k2])
{
tmp = g[u][k1];
break;
}
}
if(find(u) != find(v)) puts("zero");
else if(tmp == -1) puts("one");
else if(num[tmp] == 1) puts("one");
else puts("two or more");
}
}
return 0;
}

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。