The Suspects POJ - 1611

Union后最后处理跟为0即可

#include 
#define MAX_LENGTH 30005
struct Union {int to;int rank;
};
Union Unions[MAX_LENGTH];
void init_QucikUnion(int length){for (int i = 0;i<=length;i++){Unions[i].to = i;Unions[i].rank = 0;}
}
int Find(int n){while (Unions[n].to != n)n = Unions[n].to ;return n;
}
void Union(int i,int j){i = Find(i);j = Find(j);if (Unions[i].rank > Unions[j].rank) {Unions[j].to = i;} else {Unions[i].to = j;if (Unions[i].rank == Unions[j].rank) Unions[j].rank++;}
}int main()
{int N,M;while (scanf("%d%d",&N,&M) != EOF && (N != 0 || M != 0)){init_QucikUnion(N);Unions[0].rank = 30005;for (int i = 0;i<M;i++){int NS;scanf("%d",&NS);int numbers[30005];for (int j = 0;j<NS;j++){scanf("%d",&numbers[j]);}for (int k = 1;k<NS;k++){Union(numbers[k-1],numbers[k]);}}int suspects = 1;for (int i = 1;i<N;i++)if (Find(i) == 0)suspects++;printf("%d\n",suspects++);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！