CCF CSP 201509 - 4 고속도로 [Kosaraju]

제목:

N 개의 점, M 개의 변 에 방향 그림 이 있 고 몇 쌍 (x, y) (x, y) (x, y) 이 x x x 에서 y y 까지 만족 할 수 있 으 며 y y 에서 x x x x x x x x x 까지 도 가능 하 다

.
생각:

S C SCC SCC 중 점 만 이 두 가지 가 달 할 수 있 는 성질

을 만족시킨다.

K o s a r a j u Kosaraju Kosaraju 알고리즘 으로 그림 속 의 모든 S C SCC SCC SCC 를 찾 아 그 중의 정점 대수

를 계산한다.

s i z e [i] size [i] size [i] 를 i 번 째 s c scc scc 중점 의 개수 로 설정 하면 a n s + = s i z e [i] ∗ 8727; (s i z e [i] − 1) / 2 ans + = size [i] * (size [i] - 1) / 2 ans + = size [i] ∗ (size [i] − 1) / 2

#include
#include
#include
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,tot,head[N],dfn[N],dcnt,c[N],scnt,size[N],vis[N],tot2,head2[N],ans;
struct Edge{
	int to,next;
}e[M],e2[M];
void add(int u,int v){
	e[++tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
} 
void add2(int u,int v){
	e2[++tot2].to=v;
	e2[tot2].next=head2[u];
	head2[u]=tot2;
}
void dfs1(int x){
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!vis[y]) dfs1(y);
	}
	dfn[++dcnt]=x;
}
void dfs2(int x){
	c[x]=scnt;size[scnt]++;
	for(int i=head2[x];i;i=e2[i].next){
		int y=e2[i].to;
		if(!c[y]) dfs2(y);
	}
}
int main(){
	cin>>n>>m;
	for(int u,v,i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);add2(v,u);		
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfs1(i);
	}
	for(int i=n;i>=1;i--){
		if(!c[dfn[i]]) ++scnt,dfs2(dfn[i]);
	}
	for(int i=1;i<=n;i++){
		int x=size[i];
		ans+=x*(x-1)/2;
	}
	cout<<ans<<endl;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CCF-201509-4-고속도로

이 문제는 강연통분량을 찾고 그림의 모든 강연통분량을 찾으며 각 분량의 도시 대수를 계산하여 답을 얻어야 한다는 것이 분명하다.도시 쌍을 계산하는 방법은 강연통분량의 결점수*(강연통분량의 결점-1)/2 python ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

CCF CSP 201509 - 4 고속도로 [Kosaraju]

좋은 웹페이지 즐겨찾기