너와 나의 스토리

문제: https://www.acmicpc.net/problem/4013 문제 풀이: https://hororolol.tistory.com/116랑 거의 비슷한 문제 다른점은 현재 위치에 레스토랑이 있다고 바로 break하는 것이 아니라 최대값을 찾을 때까지 연산함 소스 코드: int n, m, cost[500001], p[500001], scc[500001],dist[500001], res; bool visit[500001], rest[500001]; vector adj, adj2, scc_adj; stack st; void dfs(int v) { visit[v] = true; for (int i : adj[v]) { if (visit[i]) continue; dfs(i); } st.push(v); }..

문제: https://www.acmicpc.net/problem/2152 문제 풀이: scc로 묶어서 간선 만듦 시작점과 끝점의 scc가 같으면 그 scc의 개수 출력 다르면 bfs돌려서 출력 소스 코드: int n, m,s,k, p[10001],scc[10001],dist[10001]; bool visit[10001]; vector adj,adj2,scc_adj; stack st; void dfs(int v) { visit[v] = true; for (int i : adj[v]) { if (visit[i]) continue; dfs(i); } st.push(v); } void rdfs(int v, int t) { visit[v] = true; p[v] = t; scc[t]++; for (int i : ..

문제: https://www.acmicpc.net/problem/3977 문제 풀이: scc를 구하는데 각 점들의 scc번호를 p배열에 저장함 scc를 구하는 dfs 중 a->b를 가리켰는데 b가 이미 visit이라면 case1: b가 다른 scc인 경우 (p[a]!=p[b]) degree[a]++ case2: b가 같은 scc인 경우는 그냥 패스 이렇게 했을 때 degree가 0인 scc가 한 개이면 그 scc를 정렬해서 출력하면 되고 두 개 이상이면 "Confused" 출력 소스 코드: int tc, n, m,p[100001],degree[100001]; bool visit[100001]; vector adj,adj2; stack st; vector scc; void dfs(int v,bool t) ..

문제: https://www.acmicpc.net/problem/4196 문제풀이: dfs돌려서 stack에 정점들 쌓아주고 stack에서 정점 빼주면서 다시 dfs 돌리면서 visit해줌 stack에서 뺀 정점이 이미 visit되어 있으면 다시 빼고 아니면 res++해주고 dfs 돌림 * https://hororolol.tistory.com/94 > tc; while (tc--) { cin >> n >> m; memset(visit, false, sizeof(visit)); int res = 0; adj.clear(); adj.resize(n + 1); for (int i = 0; i > q >> w; adj[q].push_back(w); } for (i..

문제: https://www.acmicpc.net/problem/6543 문제 설명: bottom(G) 어떤 정점에서 출발하여 갈 수 있는 모든 정점에서 돌아 올 수 있는 정점들의 집합 ex) 5 5 1 2 2 3 3 1 3 4 4 5 1->2->3->1로 1,2,3이 bottom(G) 속할 것 같아 보이지만 3->4->5로 가고 4나 5에서 1,2,3으로 올 수 없으므로 bottom(G)에 속하지 않음 5는 출발한 정점이 없으므로 bottom(G)에 속함 문제 풀이: 알고리즘 - scc 1. dfs 돌려서 정점 stack에 쌓기 2. scc를 저장하는데 현재까지 저장된 res(scc)의 크기가 t라고 했을 때, 지금 rdfs를 돌려서 얻은 scc는 res[t]이후에 쌓이게 된다 그러므로 한 번 scc ..

문제: https://www.acmicpc.net/problem/15783 문제 풀이: 1. dfs를 돌려서 스택에 정점들을 넣는다 2. 스택을 pop하면서 그 정점을 시작으로 dfs 돌림 -> visit하면서 이미 다른 정점을 시작으로 방문한 점들은 그냥 pop만 해주고 방문 안한 것들만 cnt++해줌 소스 코드: int n, m,cnt; bool visit[100001]; vector adj; stack st; void dfs(int v,bool t) { if (visit[v]) return; visit[v] = true; for (int i : adj[v]) { dfs(i,t); } if(t) st.push(v); } int main() { ios::sync_with_stdio(false); cin..