백준 11266 : 단절점, 11400 : 단절선, 10891 : Cactus? Not cactus?

박명훈·2020년 3월 18일
0

ps

목록 보기
15/29

그래프 단절점, 단절선에 대한 개념을 여기서 접하게 되었고, 연습하는 겸 문제를 풀어보았다.

11266 단절점
문제 링크

주어진 그래프를 DFS트리로 바꾸면서 단절점 여부를 판단할 건데, 어떠한 점이 단절점인지 확인하기 위해서는 그 점의 모든 자식들이 그 점을 이용하지 않고 그 점의 부모 이상으로 역으로 올라갈 수 있는지(back edge 통해)를 판단해주면 된다. scc알고리즘과 비슷한 느낌으로 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <stack>
 
using namespace std;
 
typedef pair<int,int> pii;
typedef long long ll;
 
const int INF = 987654321;
const int mod = 1e9 + 7;
 
int v,e;

vector<vector<int>> edge;
vector<int> discovered;
vector<bool> iscut;
int discoveredcnt = 0;

int dfs(int a,int prev,bool isroot)
{
    discovered[a] = discoveredcnt++;
    int ret = INF;
    int cnt = 0;

    for(auto next : edge[a])
    {
        if(discovered[next] == -1)
        {
            int child = dfs(next,a,false);
            cnt++;
            ret = min(ret,child);
            if(!isroot && child >= discovered[a])
            {
                iscut[a] = true;
            }
        }
        else if(next != prev)
        {
            ret = min(ret,discovered[next]);
        }
    }
    
    if(isroot && cnt >= 2)
    {
        iscut[a] = true;
    }
    return ret;
}

int main(int argc, char** argv) {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>v>>e;

    edge = vector<vector<int>>(v);
    discovered = vector<int>(v,-1);
    iscut = vector<bool>(v,false);

    for(int i= 0;i<e;i++)
    {
        int v1,v2;
        cin>>v1>>v2;

        v1--; v2--;

        edge[v1].push_back(v2);
        edge[v2].push_back(v1);
    }
    
    for(int i = 0;i<v;i++)
    {
        if(discovered[i] == -1)
        {
            dfs(i,i,true);
        }
    }

    vector<int> ans;
    for(int i = 0;i<v;i++)
    {
        if(iscut[i])
        {
            ans.push_back(i+1);
        }
    }

    cout<<ans.size()<<"\n";
    for(auto elem : ans)
    {
        cout<<elem<<" ";
    }
	return 0;
}

11400 단절선
문제 링크

단절선은 아까 썼던 dfs함수를 살짝 응용해서 해결할 수 있다. cur과 prev가 있을 때, cur의 자식들이 cur-prev간선을 이용하지 않고 discovered가 discovered[prev]보다 같거나 작은 정점까지 도달할 수 있지 않다면, cur-prev는 단절선이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <stack>
 
using namespace std;
 
typedef pair<int,int> pii;
typedef long long ll;
 
const int INF = 987654321;
const int mod = 1e9 + 7;
 
int v,e;

vector<vector<int>> edge;
vector<int> discovered;
vector<pii> ans;
int discoveredcnt = 0;

int dfs(int cur,int prev)
{
    discovered[cur] = discoveredcnt++;
    
    int ret = INF;

    bool flag = false;
    for(auto next : edge[cur])
    {
        if(next == prev) continue;

        if(discovered[next] == -1)
        {
            ret = min(ret,dfs(next,cur));
        }
        else
        {
            ret = min(ret,discovered[next]);
        }
    }
    
    if(cur != prev && ret >= discovered[cur]) ans.push_back({min(cur,prev),max(cur,prev)});
    return ret;
}

int main(int argc, char** argv) {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>v>>e;

    edge = vector<vector<int>>(v);
    discovered = vector<int>(v,-1);

    for(int i= 0;i<e;i++)
    {
        int v1,v2;
        cin>>v1>>v2;

        v1--; v2--;

        edge[v1].push_back(v2);
        edge[v2].push_back(v1);
    }
    
    for(int i = 0;i<v;i++)
    {
        if(discovered[i] == -1)
        {
            dfs(i,i);
        }
    }

    sort(ans.begin(),ans.end());

    cout<<ans.size()<<"\n";
    for(auto elem : ans)
    {
        cout<<elem.first+1<<" "<<elem.second+1<<"\n";
    }

	return 0;
}

10891 - Cactus? Not cactus?
문제 링크

각 정점에 대해 사이클이 하나 이하 있는지를 판단하는 문제이다. 각 정점에 대해 사이클이 두개 이상이 돌기 위한 조건으로는 두가지를 생각해 볼 수 있다.

1)사이클이 한 가지에서 생기는 경우

이런 식으로 사이클이 두개 이상 생기는 것에 대해서 생각해 볼 수 있는데, dfs를 해주면서 back edge가 있는 정점에 대해서 그 자식들이 back edge를 이용해서 그 정점, 혹은 그 이전의 정점까지 갈 수 있으면 겹치는 부분이 생기면서 사이클이 두개 생기는 것을 알 수 있다.

2)두개이상 가지에서 생기는 경우

이런 식으로 두 개의 사이클이 생길수도 있다. 따라서 각 정점에서 자식들 중 back edge를 통해 자신, 혹은 보다 더 이전에 방문한 정점까지 갈 수 있는 것이 몇개인지 저장해서 구한다. 2 이상이라면 사이클이 두개이상 생성되므로 Not Catcus를 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <stack>
 
using namespace std;
 
typedef pair<int,int> pii;
typedef long long ll;
 
const int INF = 987654321;
const int mod = 1e9 + 7;
 
int n,m;
vector<vector<int>> edge;
vector<int> backcnt;
vector<int> discovered;
bool iscat = true;
int discovcnt = 0;

int dfs(int cur,int prev)
{
    discovered[cur] = discovcnt++;
    int ret = INF;
    bool isback = false;
    int retemp = INF;
    int cnt = 0;
    for(auto next : edge[cur])
    {
        if(next == prev) continue;
        
        if(discovered[next] == -1)
        {
            int child = dfs(next,cur);
            if(child <= discovered[cur] ) cnt++;
            ret = min(ret,child);
            
        }
        else if(discovered[cur] > discovered[next])
        {
            retemp = min(retemp,discovered[next]);
            isback = true;
        }
    }

    if((isback && ret <= discovered[cur]) || cnt > 1) 
    {
        iscat = false;
    }

    ret = min(ret,retemp);

    return ret;
}

int main(int argc, char** argv) {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>m;
    edge = vector<vector<int>>(n);
    backcnt = vector<int>(n,0);
    discovered = vector<int>(n,-1);

    for(int i = 0;i<m;i++)
    {
        int v1,v2;
        cin>>v1>>v2;
        v1--;v2--;
        edge[v1].push_back(v2);
        edge[v2].push_back(v1);
    }

    for(int i = 0;i<n;i++)
    {
        if(discovered[i] == -1)
        {
            dfs(i,i);
        }
    }

    if(iscat) cout<<"Cactus";
    else cout<<"Not cactus";
	return 0;
}

0개의 댓글