HUD(2444)
n 명, m 명의 친구 관 계 를 주 고 두 조로 나 눌 수 있 는 지 판단 하 게 해 줄 게 요.
그리고 안에 서 는 아무 도 모 릅 니 다.
하면, 만약, 만약...
해법
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int v,u;
int next;
}V[1000*1000];
int n,m;
int tol;
int head[1000];
int col[1000];
int link[1000];
bool vis[1000];
void init()
{
int tol=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
V[tol].v=v;
V[tol].u=u;
V[tol].next=head[u];
head[u]=tol++;
int t=u;u=v;v=t;
V[tol].v=v;
V[tol].u=u;
V[tol].next=head[u];
head[u]=tol++;
}
bool dfs(int u)
{
vis[u]=1;
for(int k=head[u];k!=-1;k=V[k].next)
{
int v=V[k].v;
if(!vis[v])
{
vis[v]=1;
if(link[v]==-1||dfs(link[v]))
{
link[v]=u;
return true;
}
}
}
return false;
}
int match()
{
int ans=0;
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
bool bldfs(int u,int co)
{
int i,v;
col[u]=co;
for(i=head[u];i!=-1;i=V[i].next)
{
v=V[i].v;
if(col[v]==co)
return false;
if(col[v]==-1&&!bldfs(v,co^1))
return false;
}
return true;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
init();
int u,v;
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
memset(col,-1,sizeof(col));
int flag=0;
for(int i=1;i<=n;i++)
{
if(col[i]==-1)
if(!bldfs(i,1))
{
flag=1;
break;
}
}
if(flag==1)
printf("No
");
else
{
int ans=match();
printf("%d
",ans/2);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.