Description
Input
nr_of_vertices
vertex:(nr_of_successors) successor1 successor2 ... successorn
...
where vertices are represented as integers from 1 to n ( n <= 900 ). The tree description is followed by a list of pairs of vertices, in the form:
nr_of_pairs
(u v) (x y) ...
The input file contents several data sets (at least one).
Note that white-spaces (tabs, spaces and line breaks) can be used freely in the input.
Output
For example, for the following tree:
Sample Input
5 5:(3) 1 4 2 1:(0) 4:(0) 2:(1) 3 3:(0) 6 (1 5) (1 4) (4 2) (2 3) (1 3) (4 3)
Sample Output
2:1 5:5
Hint
#include <stdio.h>
#include <string.h>
#define NN 902
using namespace std;
typedef struct node{
int v;
struct node *nxt;
}NODE;
NODE edg1[NN * 2], edg2[NN * 1000];//数组要开大点
NODE *Link1[NN], *Link2[NN];
int idx1, idx2, N, M;
int fat[NN];
int vis[NN];
int cnt[NN];
void Init(NODE *Link[], int &idx){
memset(Link, 0, sizeof(Link[0]) * (N + 1));
idx = 0;
}
void Add(int u, int v, NODE edg[], NODE *Link[], int & idx){
edg[idx].v = v;
edg[idx].nxt = Link[u];
Link[u] = edg + idx++;
edg[idx].v = u;
edg[idx].nxt = Link[v];
Link[v] = edg + idx++;
}
int find(int x){
if(x != fat[x]){
return fat[x] = find(fat[x]);
}
return x;
}
void Tarjan(int u){
vis[u] = 1;
fat[u] = u;
for (NODE *p = Link2[u]; p; p = p->nxt){
if(vis[p->v]){
cnt[find(p->v)]++;
}
}
for (NODE *p = Link1[u]; p; p = p->nxt){
if(!vis[p->v]){
Tarjan(p->v);
fat[p->v] = u;
}
}
}
int main() {
int i, u, v, n, root;
int flag[NN];
while(scanf("%d", &N) != EOF){
Init(Link1, idx1);
memset(flag, 0, sizeof(flag));
for (i = 1; i <= N; i++){ //数据的读入方式很不错啊
scanf("%d", &u);
while(getchar() != '(');
scanf("%d", &n);
while(getchar() != ')');
while(n--){
scanf("%d", &v);
flag[v] = 1;
Add(u, v, edg1, Link1, idx1);
}
}
scanf("%d", &M);
Init(Link2, idx2);
for (i = 1; i <= M; i++){
while(getchar() != '(');
scanf("%d%d", &u, &v);
while(getchar() != ')');
Add(u, v, edg2, Link2, idx2);
}
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= N; i++){// 第一个结点不一定是根结点
if(flag[i] == 0) break;
}
root = i;
Tarjan(root);
for (i = 1; i <= N; i++){
if(cnt[i]){
printf("%d:%d\n", i, cnt[i]);
}
}
}
return 0;
}