TIOJ 1451 八卦傳播系統

poao899    3516K    398MS    G++     1.29K     2009-11-06 08:55:02                                     .


唔嘎如果沒有長期被捏可能想不到Q

題目：

給一張有向圖，請問最少要多少個起點才能遍歷每個點。

v, e <= 100,000






















解法：

一直被捏是SCC但是詳細怎麼寫現在才弄出來

縮點之後就是DAG了

所以沒有入分支度的點就一定得當起點








//***************************************************

#include<stdio.h>
#define MAX 100100
int getint(){
	int g=0,c=getchar();
	while(c==10||c==32||c==9)c=getchar();
	while(c>='0'&&c<='9'){
		g=g*10+c-48;
		c=getchar();
	}
	return g;
}
struct edge{
	int j;
	edge *next;
}E[MAX],Er[MAX],*V[MAX],*Vr[MAX];
int stamp[MAX],cnt;
bool visited[MAX];
int scc,belong[MAX],inscc;
bool noindeg;
int n,m,a,b;
void dfs(int start){
	edge *p=V[start];
	visited[start]=1;
	while(p!=NULL){
		if(!visited[p->j]){
			dfs(p->j);
		}
		p=p->next;
	}
	stamp[cnt++]=start;
}
void dfsr(int start){
	edge *p=Vr[start];
	visited[start]=1;
	belong[start]=inscc;
	while(p!=NULL){
		if(!visited[p->j]){
			dfsr(p->j);
		}
		else if(belong[p->j]!=inscc){
			noindeg=0;
		}
		p=p->next;
	}
}
main(){
	n=getint();
	m=getint();
	//construct a graph and a reverse graph
	for(int i=0;i<m;i++){
		a=getint();
		b=getint();
		E[i].j=b;
		edge *p=V[a];
		V[a]=&E[i];
		E[i].next=p;
		
		Er[i].j=a;
		p=Vr[b];
		Vr[b]=&Er[i];
		Er[i].next=p;
	}
	//正的一次
	for(int i=1;i<=n;i++)
		if(!visited[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		visited[i]=0;
	//反的一次
	for(int i=n-1;i>=0;i--){
		//printf("%d: %d\n",i,stamp[i]);
		if(!visited[stamp[i]]){
			++inscc;
			noindeg=1;
			dfsr(stamp[i]);
			scc+=noindeg;
		}
	}
	printf("%d\n",scc);
}