Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WHY WA?????

Posted by snowflysky at 2009-08-03 08:02:07 on Problem 2186
#include<iostream>
#include<stack>
/*
#include<vector>
*/
#include<memory.h>
#define MAXN 10000
using namespace std;
class edge{
	public:
		int y;
	    edge *next;
		edge(int _y,edge *_next):y(_y),next(_next){}
} *hLink[MAXN+1];
/*
class SCC{
	public:
		bool isin[MAXN+1];
	    int indegree,outdegree;
		SCC(bool _isin[]){
			memcpy(isin,_isin,MAXN+1);
		}
};
vector<SCC> vcs;
*/
stack<int> stk;
int SCCnum[MAXN+1],SCCmember[MAXN+1];
int odegree[MAXN+1];
int n,m,dfn[MAXN+1],L[MAXN+1],num,SCCCnt,_tot;
bool instk[MAXN+1];
void Tarjan(int u){
	dfn[u]=L[u]=++num;
	stk.push(u);
	instk[u]=true;
	for (edge *p=hLink[u];p;p=p->next)
		if (!dfn[p->y]){
		   Tarjan(p->y);
		   L[u]=min(L[u],L[p->y]);
	    }
	    else if (instk[p->y]) L[u]=min(L[u],dfn[p->y]);
	if (dfn[u]==L[u]){
    	int v;
		do{
			v=stk.top();
			SCCnum[v]=SCCCnt;
			stk.pop();
		} while (u!=v);
		++SCCCnt;
/*
		bool t[MAXN+1];
		memset(t,false,sizeof(t));
		do{
			int v=stk.top();
			t[v]=true;
			stk.pop();
		} while (u!=v);
		SCC s(t);
		vcs.push_back(s);
*/
	}
}
int main (void){
	cin>>n>>m;
	for (int i=1;i<=n;++i) hLink[i]=NULL;
	for (int i=0;i<m;++i){
		int a,b;
		cin>>a>>b;
		hLink[a]=new edge(b,hLink[a]);
	}
	for (int i=1;i<=n;++i)
		if (!dfn[i]) Tarjan(i);
	for (int i=1;i<=n;++i){
		++SCCmember[SCCnum[i]];
		for (edge *p=hLink[i];p;p=p->next)
		    if (SCCnum[p->y]!=SCCnum[i]) ++odegree[SCCnum[i]];
	}
	for (int i=0;i<SCCCnt;++i)
		if (!odegree[i]) _tot+=SCCmember[i];
	cout<<_tot<<endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator