[ BOJ 백준 2150번 - Strongly Connected Component ] 해설 및 코드
https://www.acmicpc.net/problem/2150 목적 SCC를 구하자. 접근법 1. SCC를 구하는 기본 문제이며, kosaraju 알고리즘을 적용한다. 2. 아래는 tarjan 알고리즘을 적용해보았다. #include #define f(i,l,r) for(int i=l;i>v>>e; adj.assign(v+1, vector()); rev.assign(v+1, vector()); while(e--){ int a,b;cin>>a>>b; adj[a].push_back(b); rev[b].push_back(a); } f(i,1,v)if(!vis[i])dfs(i,adj,order); reverse(order.begin(),order.end()); memset(vis,false,sizeof(vi..
[ BOJ 백준 6497번 - 전력난 ] 해설 및 코드
https://www.acmicpc.net/problem/6497 목적 임의의 두 집 사이에 불이 켜져 있는 길이 있어야 할 때, 필요한 길만 남겨 절약할 수 있는 최대 액수를 구하자. 접근법 1. MST를 구하는 문제이며, 크루스칼 알고리즘을 적용하며 해결하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #define f(i,l,r) for(int i=l;in; if(!m&&!n)break; f(i,0,n)cin>>ed[i].a>>ed[i].b>>ed[i].c,ans+=ed[i].c; sort(ed,ed+n); memset(p,-1,4*m); f(i..
[ BOJ 백준 1197번 - 최소 스패닝 트리 ] 해설 및 코드
https://www.acmicpc.net/problem/1197 목적 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하자. 접근법 1. 크루스칼 알고리즘의 기본 응용 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #define f(i,l,r) for(int i=l;ie; memset(p,-1,sizeof(int)*(v+1)); f(i,0,e)cin>>ed[i].a>>ed[i].b>>ed[i].c; sort(ed,ed+e); int ans=0; f(i,0,e){ int ra=find(ed[i].a),rb=find(ed[i].b); i..
