团伙封锁阳光大学(代码片段)

关键词：

团伙

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e5+7;
int fa[maxn],en[maxn],size[maxn];
int n,m;
int find(int x)  
  
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]); 


void merge(int x, int y)

    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    if (size[fx]<size[fy]) swap(fx, fy);  
    size[fx]+=size[fy];
    fa[fy] = fx;
    return;


int main()
    cin>>n>>m;
    for(int i = 1;i <= n;i ++)
        fa[i] = i;
        size[i]=1;
    
    for(int i = 1;i <= m;i ++)
        char a;int b,c;
        cin>>a>>b>>c;
        if(a == ‘F‘)
            merge(b,c);
            if(!en[b]&&!en[c]) merge(en[b],en[c]);
        
        if(a == ‘E‘)
            if(en[c]!=0) merge(b,en[c]); 
            if(en[b]!=0) merge(c,en[b]);
            en[b]=c;en[c]=b;
        
    
    int ans = 0;
    for(int i = 1;i <= n;i ++)
        if(fa[i] == i) ans++;        
    
    cout<<ans<<endl;
    return 0;

封锁阳光大学

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100007;
int enm[maxn],fa[maxn],ff,ans,sz[maxn];
bool vis[maxn];
int find(int a)
    if(fa[a]==a) return fa[a];
    return fa[a]=find(fa[a]);

void merge(int a,int b)
    int aa=find(a);
    if(aa!=b)
        fa[b]=aa;
        sz[aa]+=sz[b];
    

int main()
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) sz[i]=1;fa[i]=i;
    for(int i=1;i<=m;i++)
        int u,v;cin>>u>>v;
        int uu=find(u),vv=find(v);
        if(uu!=vv)
            if(enm[u]) merge(enm[u],vv);
            if(enm[v]) merge(enm[v],uu);
            enm[u]=vv;enm[v]=uu;
        
        if(uu==vv)
            cout<<"Impossible"<<endl;
            return 0;
        
    
    for(int i=1;i<=n;i++)
        int ff=find(i);
        if(!vis[ff])
            int pp=find(enm[i]);
            vis[ff]=true;vis[pp]=true;
            ans+=min(sz[ff],sz[pp]);
        
    
    cout<<ans<<endl;
    return 0;
    

洛谷p1330封锁阳光大学(代码片段)

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁 查看详情

luogup1330封锁阳光大学(代码片段)

解题思路显然相邻的两个点是不能够同时存在河蟹的，那就对每两个相邻的点进行染色操作，一个染成黑点，一个染成白点。一个很容易想到的事实就是如果在染色的过程中对某一点的操作和之前染的色冲突，那么河蟹就无法成... 查看详情

luogup1330封锁阳光大学(代码片段)

嘟嘟嘟 又刷了一道水题……很显然只要判断这个图是否是二分图就行了，判断方法就是染色。如果对于边(u->v)，两个点颜色相同，那么就说明图中存在奇环，不是二分图。统计答案的时候输出两种颜色较小的就行了。需要... 查看详情

p1330封锁阳光大学(代码片段)

传送门思路：　　依题意可知，在图中的每一条边有且只有一个点被选中（阻止老曹刷街），那么就可以对其采取二分图染色，一条边中：一个点为黑色，另一个点为白色；如果一条边中的两个端点的颜色相同，则说明无解，输... 查看详情

luogup1330封锁阳光大学(黑白染色)(代码片段)

题意：无向图，给一个顶点染色可以让他相邻的路不能通过，但是相邻顶点不能染色，求是否可以让所有的路不通，如果可以求最小染色数。思路：对于无向图中的每一个连通子图，都只有两种染色方法，或者染不了，直接搜即... 查看详情

p1330封锁阳光大学-二分图染色(代码片段)

传送门根据题意可知二分图染色。若无法被染成二分图，输出Impossible；反之，对于每个二分图，记录两种颜色的点的个数，取min后记录答案中。注意，图可能不连通。因此对于每个二分图，都要进行取min操作，而不是对整个图... 查看详情

luogup1330封锁阳光大学dfsbycellur925(代码片段)

题目传送门这道题我们很容易去想到二分图染色，但是这个题好像又不是一个严格的二分图。开始的思路：dfs每个点，扫与他相邻的每个点，如果没访问，染相反颜色；如果访问过，进行检查，如果不可行，直接结束程序。每dfs... 查看详情

p1330封锁阳光大学

P1330封锁阳光大学题目描述曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个... 查看详情

洛谷——p1330封锁阳光大学

P1330封锁阳光大学题目描述曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个... 查看详情

洛谷1330封锁阳光大学

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连... 查看详情

p1330封锁阳光大学（染色问题）

 P1330封锁阳光大学题目描述曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，... 查看详情

luogup1330封锁阳光大学x

 P1330封锁阳光大学题目描述曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，... 查看详情

封锁阳光大学-二分图染色

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连... 查看详情

洛谷p1330封锁阳光大学(二分图染色)

P1330封锁阳光大学题目描述曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个... 查看详情

洛谷——p1330封锁阳光大学

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连... 查看详情

洛谷p1330封锁阳光大学

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连... 查看详情

洛谷p1330封锁阳光大学

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连... 查看详情

洛谷p1330封锁阳光大学

...的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连... 查看详情