落絮飞雁

Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( #include #include int father[1001]; int FindGF(int a)//找祖父节点 { while (father[a] != a) a = father[a]; return a; } void Branch(int a, int b)//合并不同的祖父节点 { int fx, fy; fx = FindGF(a); fy = FindGF(b); if (fx != fy) father[fx] = fy; } int main() { int n, m, i, x, y, ans; while (scanf(“%d”, &n) && n != 0) { for (i = 1; i

Problem Description
In order to get rid of Conan, Kaitou KID disguises himself as a teacher in the kindergarten. He knows kids love games and works out a new game called “hand in hand”.

Initially kids run on the playground randomly. When Kid says “stop”, kids catch others’ hands immediately. One hand can catch any other hand randomly. It’s weird to have more than two hands get together so one hand grabs at most one other hand. After kids stop moving they form a graph.

Everybody takes a look at the graph and repeat the above steps again to form another graph. Now Kid has a question for his kids: “Are the two graph isomorphism?”

Input
The first line contains a single positive integer T( T D_Double同学的。
首先考虑到每个节点的度数最多只能是2（每人两只手）。最终这些学生可能会被分成多组，每组是一个环形圆圈，或者是一条链。

题目要判断两个已经连好的图是否是”同构图”,。这里所谓的同构图是指两个图组成的不同的圆圈，链条，他们各个所对应的数量都是相等的。

那么我们只需要用并查集把连这的都合并起来，如果发现有环，就进行标识。然后把两个图的并查集按照每颗树的节点个数大小排序，如果个数相同，那么有环的都放在前面。 然后，只要一一比较两个已排序的数组，只要发现有一个是不同的，就不是同构图。

代码：

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxN = 10001;

int n, m, n2, m2;
int father[maxN], PT[maxN], isCircle[maxN];
//memset(0, isCircle, sizeof(isCircle));
struct node
{
    int num, isCircle;
    friend bool operator b.num;
        return a.isCircle>b.isCircle;
    }
}an[maxN], bn[maxN];

int findset(int x)
{
    if (x == father[x]) return x;
    return father[x] = findset(father[x]);
}
void Union(int x, int y)
{
    x = findset(x); y = findset(y);
    if (x == y)
    {
        isCircle[x] = 1;
        return;
    }
    if (PT[x]>PT[y])
    {
        father[y] = x;
        PT[x] += PT[y];
    }
    else
    {
        father[x] = y;
        PT[y] += PT[x];
    }
}

int main()
{
    int t, ncase = 1;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        memset(isCircle, 0, sizeof(isCircle));
        for (int i = 1; i 
参考了一部分代码。心急火燎的赶去看谷歌IO了~