算法笔记--二分图判定-白红宇

算法笔记--二分图判定

阅读量：6270 次

发布时间：2019-06-22

本文共 2251 字，大约阅读时间需要 7 分钟。

算法笔记

挑战程序设计p98

#include
     
      using namespace std; #define ll long long#define ls rt<<1,l,m#define rs rt<<1|1,m+1,rconst int INF=0x3f3f3f3f;const int N=1e5+5;vector
      
       g[N];int color[N]={
   0};bool dfs(int u, int c){    color[u]=c;    for(int i=0;i
       
        >n;    for(int i=0;i
        
         >t;        while(t--)        {            int a;            cin>>a;            g[i].push_back(a);        }    }    　　for(int i=0;i

例题1：

代码：

#include
      
       using namespace std;#define ll long long#define ls rt<<1,l,m#define rs rt<<1|1,m+1,rconst int INF=0x3f3f3f3f;const int N=1e5+5;vector
       
        g[N];int color[N]={
    0};bool dfs(int u, int c){    color[u]=c;    for(int i=0;i
        
         >t;        while(t--)    {        cin>>n>>m;        for(int i=1;i<=n;i++)g[i].clear();        memset(color,0,sizeof(color));                for(int i=0;i
         
          >u>>v;            g[u].push_back(v);            g[v].push_back(u);         }                bool flag=true;        for(int i=1;i<=n;i++)        {            if(color[i]==0)            {                if(!dfs(i,1))                {                    flag=false;                }            }        }        if(flag)cout<<"Correct"<

View Code

例题2：

代码：

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;vector
       
        g[N];//bool vis[N]={false};int color[N]={
    0} ;/*void dfs(int o,int u)//联通性判定 {    vis[u]=true;    for(int &v:g[u])if(v!=o&&!vis[v])dfs(u,v);}*/bool DFS(int u,int c)//二分图判定 {    color[u]=c;    for(int &v:g[u])    {        if(color[v]==c)return false;        if(color[v]==0&&!DFS(v,-c))return false;    }    return true;} int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int t,n,m,s,u,v,cse=1;    cin>>t;    while(t--)    {        cin>>n>>m>>s;        for(int i=0;i
        
         >u>>v,g[u].pb(v),g[v].pb(u);        cout<<"Case "<
         
          <<": ";        //mem(vis,false);        mem(color,0);        //dfs(0,0);            bool flag=true;        //for(int i=0;i