Problem - 1702E - Codeforces
思路:这道题自己没磕出来思路,大体上就是,先将节点相互连接起来,{1,2}{2,1},{3,4}{4,3}当形成的环是偶数的时候,既可以间隔选择形成二分图,若能形成二分图,则两边选择的多米诺牌都是独立的,如果不能形成二分图,那么证明多米诺牌出现了重复现象。
输入的时候特判自环,还有特判一下每个数字是否出现超过两次
Solution:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
/* * |~~~~~~~| * | | * | | * | | * | | * | | * |~.\\\_\~~~~~~~~~~~~~~xx~~~ ~~~~~~~~~~~~~~~~~~~~~/_//;~| * | \ o \_ ,XXXXX), _..-~ o / | * | ~~\ ~-. XXXXX`)))), _.--~~ .-~~~ | * ~~~~~~~`\ ~\~~~XXX' _/ ';)) |~~~~~~..-~ _.-~ ~~~~~~~ * `\ ~~--`_\~\, ;;;\)__.---.~~~ _.-~ * ~-. `:;;/;; \ _..-~~ * ~-._ `'' /-~-~ * `\ / / * | , | | * | ' / | * \/; | * ;; | * `; . | * |~~~-----.....| * | \ \ * | /\~~--...__ | * (| `\ __-\| * || \_ /~ | * |) \~-' | * | | \ ' * | | \ : * \ | | | * | ) ( ) * \ /; /\ | * | |/ | * | | | * \ .' || * | | | | * ( | | | * | \ \ | * || o `.)| * |`\\) | * | | * | | */ #include<iostream> #include<queue> #include<vector> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<unordered_map> #include<map> // #pragma GCC optimize(3) using namespace std; #define rep(i,x,y) for(int i=x;i<y;i++) #define scan(x) scanf("%lld",&x) #define int long long #define lowbit(x) x&(-x) //二进制最低位所代表的数 #define PI 3.1415926535 typedef pair<int,int> PII; int gcd(int a,int b){ return b>0 ? gcd(b,a%b):a; } int exgcd(int a,int b,int &x,int &y) { if(!b) { x = 1,y = 0; return a; } int d = exgcd(b,a%b,y,x); y-=a/b*x; return d; } const int N = 2e5+10; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; void init() { cin.tie(0),cout.tie(0); ios::sync_with_stdio(false); } map<int,vector<int>> mp; int color[N]; bool dfs(int u,int c) { color[u]=c; for(auto j:mp[u]) { if(!color[j]) { if(!dfs(j,3-c))return false; }else if(color[j]==c)return false; } return true; } void solve() { mp.clear(); memset(color,0,sizeof color); int n; cin>>n; bool flag = true; for(int i=0;i<n;i++) { int x,y; cin>>x>>y; mp[x].push_back(y); mp[y].push_back(x); if(x==y||mp[x].size()>2||mp[y].size()>2) { flag = false; } } if(!flag) { cout<<"NO"<<endl; return; } for(int i=1;i<=n;i++) { if(!color[i]) { if(!dfs(i,1)) { cout<<"NO"<<endl; return; } } } cout<<"Yes"<<endl; } signed main() { init(); int t; cin>>t; while(t--)solve(); }View Code
标签:return,int,Into,Two,color,mp,false,include,Split From: https://www.cnblogs.com/yeonnyuui/p/16597040.html