Graph를 이해하는 가장 좋은 방법은 내가 node가 되서 길을 걷는다 생각하면 된다.
그래서 내가 이제부터 node가 되볼게 얍!
SCC 기본 템플릿
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <limits>
#include <sstream>
#include <iomanip>
#define INF 0x3f3f3f3f // 경우에 따라 다르게
// long long 일 1e18
using namespace std;
vector<int> graph[1001];
vector<vector<int>> Vscc;
stack<int> s;
int finish[1001];
int id;
int disc[1001]; // discovery number
int dfs(int x)
{
id++;
disc[x] = id;
s.push(x);
int parent = disc[x] ;
// for(auto c : graph[x])
// {
// int y = c ;
// if(p[c] == 0)
// {
// parent = min(parent,dfs(y));
// }
// else if(finish[y] == 0)
// parent = min(parent,p[y]);
// }
for(auto y : graph[x])
{
if(disc[y] == 0)
parent = min(parent,dfs(y));
else if(finish[y] == 0 )
parent = min(parent, disc[y]);
}
if(parent == disc[x])
{
vector<int> scc;
while(1){
int t = s.top();
s.pop();
scc.push_back(t);
finish[t] = 1;
if(t == x)
break;
}
Vscc.push_back(scc);
}
// 부모값
return parent;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m ;
cin >> n >> m ;
for(int i = 0 ; i< m; i++)
{
int x, y ;
cin >> x >> y ;
graph[x].push_back(y);
}
for(int i = 1; i<=n; i++)
{
if(disc[i] == 0)
dfs(i);
}
cout << "scc의 갯수 : " << Vscc.size() <<"\n";
for(int i = 0; i< Vscc.size(); i++)
{
for(int j = 0 ; j<Vscc[i].size(); j++)
{
cout << Vscc[i][j] <<" ";
}
cout <<"\n";
}
}
1번 node에서 dfs진입하면 id 1번을 부여받고 연결된 노드를 바라보면 2가 있으니 if 조건 문에서 2번은 방문이 안되었으니 2번으로 진입 id 2번을 부여받고 연결된 노드를 바라보면 3 있으니 if 조건 문에서 3번은 방문이 안되었으니 3번으로 진입 3번으로 진입하면 인접노드 1번이 있으니 1번은 id를 부여받았으니 parent = min(parent, disc[y]); 하면 parent가 1번이 되고 그러면 parent가 1번이면 밑에 if문은 실행 X 다시 2번으로 나오면 부모값 return하고 1번에 와서야 parent = disc[x]가 같음으로 stack에 있는 node들 빼기 다 빼면 다시 main으로 돌아가 disc 확인하면서 4번이 0임으로 dfs 4번 진입 2번과 5번 확인 하는데 2번은 if문 전부 안걸림 5번은 disc 0이라 진입 5번 7번 6번 순으로 진입후 6번에서 5번을 다시 확인 할때 disc가 있고 finish는 0이여서 확인 후 parent 5로 만들어짐 그 후 dfs전부 빠져나오면 5번에서 parent와 disc[x]가 같고 stack에는 4576 순으로 들어가있는데 하나씩 5가 빠져나올 때까지 빠지면 하나의 그룹이 완성되고 parent값고 return되면 node 4에서 parent가 4로 바뀌고 다시 parent와 disc[x]가 같아지기 때문에 하나의 그룹 완성 ... 이런식으로 진행
SCC 축약
SCC를 축약해서 하나의 새로운 super node로 바꿀 수 있다는 idea 즉 그룹은 cycle이지만 모든 SCC를 축약해서 DAG로 만들 수 있음 이거 왜하냐? 시간 단축할 수 있기 때문
DAG로 위상정렬 DP를 사용해서 문제 풀이가능하다는것 !!!
예시문제 CECS CoinCollector
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <limits>
#include <sstream>
#include <iomanip>
#define INF 0x3f3f3f3f // 경우에 따라 다르게
// long long 일 1e18
using namespace std;
vector<int> g[100001];
int coin[100001];
long long new_coin[100001];
int n, m;
vector<int> ng[100001];
int p[100001];
int visited[100001];
stack<int> s;
int id;
// vector<vector<int>> SCC;
int group[100001];
int scc_count = 1;
int indegree[100001];
int check[100001];
long long dp[100001];
int dfs(int x)
{
id++;
p[x] = id;
s.push(x);
int parent = p[x];
for (auto c : g[x])
{
if (p[c] == 0)
{
parent = min(parent, dfs(c));
}
else if (visited[c] == 0)
{
parent = min(p[c], parent);
}
}
if (parent == p[x])
{
// vector<int> scc;
while (1)
{
int t = s.top();
s.pop();
visited[t] = 1;
// scc.push_back(t);
group[t] = scc_count;
new_coin[scc_count] += coin[t];
if (t == x)
break;
}
// SCC.push_back(scc);
scc_count++;
}
return parent;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> coin[i];
}
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
for (int i = 1; i <= n; i++)
{
// dfs
if (p[i] == 0)
dfs(i);
}
for (int i = 1; i <= n; i++)
{
for (auto c : g[i])
{
if (group[i] != group[c])
{
ng[group[i]].push_back(group[c]);
indegree[group[c]]++;
}
}
}
//
queue<int> q;
for (int i = 1; i < scc_count; i++)
{
if (indegree[i] == 0)
{
q.push(i);
dp[i] = new_coin[i];
}
}
// for (int i = 1; i <= n; i++)
// {
// cout << group[i] << " ";
// }
// cout << "\n";
// cout << scc_count <<"\n";
// for(int i =1 ; i<scc_count; i++)
// {
// cout << indegree[i] <<" ";
// }
// cout <<"\n";
// for (int i = 1; i <= n; i++)
// {
// cout << p[i] << " ";
// }
// cout << "\n";
while (!q.empty())
{
int cur = q.front();
q.pop();
// cout << cur <<"\n";
for (auto c : ng[cur])
{
// cout << cur << " "<< c <<"\n";
dp[c] = max(dp[c], dp[cur] + new_coin[c]);
indegree[c]--;
if (indegree[c] == 0)
{
q.push(c);
}
}
}
long long ans = 0;
for (int i = 1; i < scc_count; i++)
{
ans = max(ans, dp[i]);
}
cout << ans << "\n";
}
살려줘
최종보스 SCPC 11회 본선 가장 긴 경로
정신나간거 같다.
문제를 전부 이해하고 보니 시험에서 이걸 구현하는거 자체가 미쳤다.
SCC 축약하고 DAG DP를 이용해서 최단거리를 구하는데 조건이 까다롭다 그냥 무작정 할 수는 없고 시작노드와 마지막노드간의 거리를 이용해서 거리를 update하는데 제정신은 아닌거 같다.
