贵州建设厅网站厅长,表情包制作在线,aspnet网站模板,wordpress 高清背景题意#xff1a; 朋友的朋友是朋友#xff0c;敌人的敌人是朋友#xff1b;朋友形成团伙#xff0c;求最多有多少团伙 种类并查集WA了一节课#xff0c;原因是#xff0c;只有那两种关系才成立#xff0c;诸如朋友的敌人是朋友之类的都不成立#xff01; 所以拆点做吧 …题意 朋友的朋友是朋友敌人的敌人是朋友朋友形成团伙求最多有多少团伙 种类并查集WA了一节课原因是只有那两种关系才成立诸如朋友的敌人是朋友之类的都不成立 所以拆点做吧 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
using namespace std;
const int N1005;
typedef long long ll;
inline int read(){char cgetchar();int x0,f1;while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}int n, m, fa[N], val[N], x, y, cc[N][2]; char s[5];
inline int find(int x) {if(x fa[x]) return x;int root find(fa[x]);val[x] ^ val[fa[x]];return fa[x] root;
}
inline void Union(int x, int y, int p) { int f1 find(x), f2 find(y);if(f1 ! f2) {fa[f1] f2;val[f1] val[x]^val[y]^p;} else {if( (val[x]^val[y]) ! p) while(1);}
}int main() {freopen(in,r,stdin);nread(); mread();for(int i1; in; i) fa[i]i;for(int i1; im; i) {scanf(%s,s); xread(), yread();Union(x, y, s[0] F ? 0 : 1);}int ans0;for(int i1; in; i) cc[find(i)][val[i]] 1;for(int i1; in; i) ans cc[i][0] cc[i][1];printf(%d,ans);
} 种类并查集 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
using namespace std;
const int N2005;
typedef long long ll;
inline int read(){char cgetchar();int x0,f1;while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}int n, m, fa[N], x, y, a[N], ans; char s[5];
inline int find(int x) {return xfa[x] ? x : fa[x]find(fa[x]);}
inline void Union(int x, int y) {x find(x), y find(y);if(x ! y) fa[x] y;
}int main() {freopen(in,r,stdin);nread(); mread();for(int i1; in*2; i) fa[i]i;for(int i1; im; i) {scanf(%s,s); xread(), yread();if(s[0]F) Union(x, y);else Union(x, yn), Union(xn, y);}for(int i1; in; i) a[i]find(i);sort(a1, a1n); ansunique(a1, a1n) - a - 1;printf(%d,ans);
} 转载于:https://www.cnblogs.com/candy99/p/6593150.html
