Sample Input
3 3 2 1 3 2 1 2 2 2 3
Sample Output
2
Sample Input 2
4 3 3 1 2 3 1 1 1 2 1 3
Sample Output 2
3
题意：
给出一个0 1矩阵，这个矩阵中每一列有且只有两个1，求这个矩阵的秩
输入一行中1的数量x，然后后面x个数代表1出现的列位置
求出这个矩阵的秩
方法：
思维 并查集
将每一列的两个1所在的行编号连一条边，然后求一下 最小生成树 就好
其实就是我们维护一个并查集，在这个并查集里面的所有点都可以两两组合形成一列，如果不在同一个集合里面，就会对答案+1
int fa[maxn]; int vis[maxn]; int n,m; inline void init(){ for(int i=0;i<maxn;i++) fa[i] = i,vis[i] = 0; } inline int findFa(int x){ if(x == fa[x]) return x; else return fa[x] = findFa(fa[x]); } int ans = 0; inline void Union(int x,int y){ int fax = findFa(x); int fay = findFa(y); if(fax == fay) return ; else{ fa[fax] = fay; ans ++; } } vector<int> vet[maxn]; int main() { cin >> m >> n; init(); for(int i=1;i<=m;i++){ int x=read; while(x --){ int val; cin >>val; vet[val].push_back(i); } } for(int i=1;i<=n;i++){ int x = vet[i][0]; int y = vet[i][1]; Union(x,y); } cout << ans << endl; return 0; }
int n, m; int fa[maxn]; int vis[maxn]; void init() { for (int i = 0; i < maxn; i++) fa[i] = i, vis[i] = 0; } inline int findFa(int x) { if (x == fa[x]) return x; else return fa[x] = findFa(fa[x]); } inline void Union(int x, int y) { int fax = findFa(x); int fay = findFa(y); if (fax == fay) return; else { fa[fax] = fay; } } int main() { cin >> m >> n; init(); for (int i = 1; i <= m; i++) { int x = read; for (int j = 1; j <= x; j++) { int t = read; if (vis[t]) Union(vis[t], i); else vis[t] = i; } } int ans = 0; for (int i = 1; i <= m; i++) { if (i == fa[i]) ans++; } cout << m - ans << endl; return 0; }
