Faint.开始的时候理解错题目意思。。。。晕。。。。。Wa了一次
结果从读之后又因为界限Wa了一次。。。。晕
47ms比较慢，可能是使用了STL的vector和stack的原因吧
部分代码如下
#include<iostream>
#include<stack>
#include<vector>
#define MAXN 1200
using namespace std;
int pre[MAXN],low[MAXN],id[MAXN];
int cnt,scnt,n,N,M;
vector<int>v[MAXN];
stack<int>ST;
struct NODE
{
int x,y;
}arr[MAXN];
void Tarjan(int x){
int t,i;
int min=low[x]=pre[x]=cnt++;
ST.push(x);
for(i=0;i<v[x].size();i++){
t=v[x][i];
if(pre[t]==-1)Tarjan(t);
if(low[t]<min)min=low[t];
}
if(min<low[x]){
low[x]=min;
return;
}
do{
id[t=ST.top()]=scnt;
low[t]=n;ST.pop();
}while(t!=x);
scnt++;
}
int SCC(){
scnt=cnt=0;
memset(pre,0xff,sizeof(pre));
memset(low,0,sizeof(low));
for(int i=0;i<n;i++)
if(pre[i]==-1)Tarjan(i);
return scnt;
}posted on 2009-06-06 20:12
KNIGHT 阅读(443)
评论(0) 编辑 收藏 引用