그래프 단절점, 단절선에 대한 개념을 여기서 접하게 되었고, 연습하는 겸 문제를 풀어보았다.
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;
}