题目1418：宝藏
时间限制：1 秒
内存限制：32 兆
特殊判题：否
- 题目描述：
-
Luke 得到一张藏宝图，藏宝图上有n个城市(编号1-n)，并且这些城市有一些道路相连着。每个城市里都有一份宝藏，并且宝藏图里已经把每个城市的宝藏位置描述得很清楚了，所以只要Luke能到达这个城市，他就一定能找到这个城市里的那份宝藏。
- 输入：
-
输入有多组，每组输入第一行为三个整数n,m,s（1<=n<=100000,0<=m<=150000）。分别表示城市的数量数和连接这些城市的路径数量,s为Luke的起点城市。接下来是m对整数v,u（1<=v,u<=n），表示从v到u有一条路径(路径为单向的)。
- 输出：
-
对于每组输入，先输出一行”Case T:” T从1开始。输出Luke最多能找到的宝藏数量。
- 样例输入：
-
4 3 11 22 32 45 4 11 22 32 43 2
- 样例输出：
-
Case 1:3Case 2:4
#include
#include #include #include #include #include #include #include #define Min(a,b) ((a)<(b))?(a):(b)#define Max(a,b) ((a)>(b))?(a):(b)#define Abs(a) ((a)>0?)(a):(-a)using namespace std;typedef long long LL ;using namespace std ;const int size=100008 ;struct EDGE{ int v ; int next ;}edge[150008] ;int id ;int vec[size] ,mystack[size] ,top;int low[size] ,dfn[size] ,idx ,num ;bool instack[size] ;int belong[size] ;inline void add_edge(int u,int v){ edge[id].v=v ; edge[id].next=vec[u] ; vec[u]=id++ ;}int sum[size] ;int s,start ;void tarjan(int u){ low[u]=dfn[u]=idx++ ; mystack[++top]=u ; instack[u]=1 ; for(int e=vec[u];e!=-1;e=edge[e].next){ int v=edge[e].v ; if(dfn[v]==-1){ tarjan(v) ; low[u]=min(low[u],low[v]) ; } else if(instack[v]) low[u]=min(low[u],dfn[v]) ; } if(low[u]==dfn[u]){ int v ; num++ ; do{ v=mystack[top--] ; instack[v]=0 ; belong[v]=num ; if(v==s) start=num ; sum[num]++ ; }while(v!=u) ; }}void init(){ idx=1 ; top=-1 ; num=0 ; id=0; memset(dfn,-1,sizeof(dfn)) ; memset(vec,-1,sizeof(vec)) ; memset(instack,0,sizeof(instack)) ; memset(sum,0,sizeof(sum)) ;}int n ;struct NEWEDGE{ int v ; int next ;}new_edge[size] ;int new_link[size] ,new_id;inline void add_new_edge(int u,int v){ new_edge[new_id].v=v ; new_edge[new_id].next=new_link[u] ; new_link[u]=new_id++ ;}int dist[size] ;int main(){ int i ,j ,m,u,v,cas=1; while(scanf("%d%d%d",&n,&m,&s)!=EOF){ init() ; while(m--){ scanf("%d%d",&u,&v) ; if(u==v) continue ; add_edge(u,v) ; } for(i=1;i<=n;i++){ if(dfn[i]==-1) tarjan(i) ; dist[i]=0 ; } new_id=0 ; memset(new_link,-1,sizeof(new_link)) ; for(u=1;u<=n;u++){ for(int e=vec[u];e!=-1;e=edge[e].next){ v=edge[e].v ; if(belong[u]!=belong[v]){ add_new_edge(belong[u],belong[v]) ; } } } queue que ; int visited[size] ; memset(visited,0,sizeof(visited)) ; que.push(start) ; dist[start]=sum[start] ; visited[start]=1 ; int ans=dist[start]; while(!que.empty()){ u=que.front() ; que.pop() ; visited[u]=0 ; for(int e=new_link[u];e!=-1;e=new_edge[e].next){ v=new_edge[e].v ; if(dist[v]