글 읽기 - 이분그래프

james1904 1년 전 0

자꾸 25%에서 틀렸다고 나오는데 어디서 틀린건지 모르겠습니다 ㅠㅠ

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;
int t, v, e;
vector<int> graph[20001];
int visited[20001];

void bfs(int n)
{
    stack<int> s;
    int color = 1;
    s.push(n);
    visited[n] = color;
    while(!s.empty())
    {
        int cur = s.top();
        s.pop();
        if (visited[cur] == 1) {
            color = 2;
        }
        else if (visited[cur] == 2) {
            color = 1;
        }
        for(auto e: graph[cur])
        {
            if(!visited[e])
            {
                visited[e] = color;
                s.push(cur);
            }
        }
    }
}

bool Bipartite_Graph()
{
    for(int i = 1; i <= v; i++)
    {
        int color = visited[i];
        for(int j: graph[i])
        {
            if(color == visited[j])
            {
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    cin>>t;
    for(int q = 0; q < t; q++)
    {
        cin>>v>>e;
        for(int i = 0; i < e; i++)
        {
            int a, b;
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        for(int i = 1; i <= v; i++)
        {
            if(!visited[i])
            {
                bfs(i);
            }
        }
        if(Bipartite_Graph())
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
        for(int i = 0; i <= v; i++)
        {
            graph[i].clear();
        }
        memset(visited, false, sizeof(visited));
    }

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이분그래프

james1904 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말