scc 문제를 해결하는 알고리즘은 kosaraju와 tarjan 두가지가 있다.
kosaraju 알고리즘은 두번의 dfs로 해결한다.
먼저 첫번째 dfs 순회를 하면서 각 정점들에 대해 방문완료시간을 계산한다.
방문완료시간을 기준으로 내림차순으로 역방향 그래프를 dfs로 순회한다.
이때 나눠지는 그룹들이 scc가 된다.
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int V,E;
vector<int> adj[100004],radj[100004];
int ft[100004];
int visit[100004],rvisit[100004];
int cnt;
int sccnum;
vector<int> sccList[100004];
int scc[100004];
int used[100004];
void dfs(int n)
{
if(visit[n]==1) return;
visit[n]=1;
for(int i=0;i<adj[n].size();i++)
{
dfs(adj[n][i]);
}
ft[++cnt]=n;
}
void rdfs(int n)
{
if(rvisit[n]==1) return;
rvisit[n]=1;
sccList[sccnum].push_back(n);
scc[n]=sccnum;
for(int i=0;i<radj[n].size();i++)
{
rdfs(radj[n][i]);
}
}
int main()
{
scanf("%d %d",&V,&E);
for(int i=1;i<=E;i++)
{
int a,b;
scanf("%d %d",&a,&b);
adj[a].push_back(b);
radj[b].push_back(a);
}
cnt=0;
for(int i=1;i<=V;i++)
{
if(!visit[i]) dfs(i);
}
sccnum=0;
for(int i=cnt;i>=1;i--)
{
if(!rvisit[ft[i]])
{
sccnum++;
rdfs(ft[i]);
}
}
for(int i=1;i<=sccnum;i++)
{
sort(sccList[i].begin(),sccList[i].end());
}
printf("%d\n",sccnum);
for(int i=1;i<=V;i++)
{
int x = scc[i];
if(!used[x])
{
used[x]=1;
for(int j=0;j<sccList[x].size();j++)
{
printf("%d ",sccList[x][j]);
}
printf("-1\n");
}
}
}구현 코드이다.
두번째 알고리즘인 tarjan 알고리즘은 한번의 dfs로 scc를 구할 수 있다.
dfs를 돌면서 정점마다 id를 매기는데, 해당 정점에서 간선을 보면서, 방문하지 않은 곳은 방문하고, 그 정점을 스택에 넣는다.
그리고 그 정점의 parid를 dfs에서 반환한다. 그 반환값과 자신의 parid 중 작은 것을 parid로 저장한다.
간선에서 이미 방문한 곳인데 scc가 아닌 경우에는 그 정점의 id와 자신의 parid 중 작은 것을 parid로 저장한다.
이렇게 모든 간선을 돌았을 때 parid와 자신의 id가 같다면 scc가 되고, 스택에 있는 점들을 자신이 나올 때까지 pop하면서 scc에 넣는다.
#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
int V,E;
stack<int>nodes;
vector<int> adj[100004];
int scc[100004];
int id[100004];
int curid,sccnum;
vector<int> sccList[100004];
int used[100004];
int dfs(int n)
{
curid++;
id[n]=curid;
int parid = id[n];
nodes.push(n);
for(int i=0;i<adj[n].size();i++)
{
int x = adj[n][i];
//방문한적 없는 경우
if(!id[x])
{
parid = min(parid, dfs(x));
}
//방문했는데 scc가 아닌 경우
else if(!scc[x])
{
parid = min(parid, id[x]);
}
}
if(parid==id[n])
{
sccnum++;
while(!nodes.empty())
{
int t = nodes.top();
nodes.pop();
sccList[sccnum].push_back(t);
scc[t]=sccnum;
if(t==n) break;
}
}
return parid;
}
int main()
{
scanf("%d %d",&V,&E);
for(int i=1;i<=E;i++)
{
int a,b;
scanf("%d %d",&a,&b);
adj[a].push_back(b);
}
curid=0;
for(int i=1;i<=V;i++)
{
if(!id[i]) dfs(i);
}
for(int i=1;i<=sccnum;i++)
{
sort(sccList[i].begin(),sccList[i].end());
}
printf("%d\n",sccnum);
for(int i=1;i<=V;i++)
{
int x = scc[i];
if(!used[x])
{
used[x]=1;
for(int j=0;j<sccList[x].size();j++)
{
printf("%d ",sccList[x][j]);
}
printf("-1\n");
}
}
}구현 코드이다.
