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

Tarjan缩点后找出度为0的强连通分量排序输出,特殊情况是强连通分量数为1直接输出1...n

Posted by speedcell4 at 2012-01-31 11:42:00 on Problem 2553
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <complex>
#include <memory>
#include <numeric>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <locale.h>

using namespace std;

const int    inf = 0x7f7f7f7f;
const int    INF = 0x7fffffff;
const double eps = 1e-8;
const double  pi = acos(-1.0);

#define _at(a,i) ((a)&(1<<(i)))
#define _not(a,i) ((a)^(1<<(i)))
#define _st1(a,i) ((a)|(1<<(i)))
#define _st0(a,i) ((a)&~(1<<(i)))
#define _lowbit(val) ((val)&(-val))

#define _gret(a,b) ((a)-(b)>eps)
#define _less(a,b) ((b)-(a)>eps)
#define _equl(a,b) (fabs((a)-(b))<eps)
#define _sign(a) (_gret(a,0.0)?1:(_equl(a,0.0)?0:-1))

#define _max(a,b) (_gret(a,b)?(a):(b))
#define _min(a,b) (_less(a,b)?(a):(b))
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
#define _clr(a,val,n) memset(a,val,sizeof(a[0])*(n))

#define _Constant_
typedef int EleType;
const int MAXV = 52000;
const int MAXE = 52000;
#define _AdjList_
struct node
{
    int v;
    EleType w;
}G[MAXE];
int index,pre[MAXV],next[MAXE];

void clear(void)
{
    index=0;
    _clr(pre,-1,MAXV);
    _clr(next,-1,MAXE);
}
void add(int u,int v,EleType w)
{
    G[index].v=v;
    G[index].w=w;
    next[index]=pre[u];
    pre[u]=index++;
}
#define _Variable_
set<int> Q;
int n,m,u,v,out[MAXV];

bool vis[MAXE];
int scc,dfn,low[MAXE],dfs[MAXE],stk[MAXE],cnc[MAXV];
#define _Tarjan_
void Tour(int u)
{
    vis[u]=true;
    stk[++stk[0]]=u;
    low[u]=dfs[u]=++dfn;
    
    for(int i=pre[u];i!=-1;i=next[i])
    {
        if(!vis[G[i].v])
        {
            Tour(G[i].v);
            low[u]=min(low[u],low[G[i].v]);
        }
        else if(!cnc[G[i].v]) low[u]=min(low[u],low[G[i].v]);
    }
    
    if(low[u]==dfs[u])
    {
        scc++;
        do
        {
            cnc[stk[stk[0]]]=scc;
        }
        while(stk[stk[0]--]!=u);
    }
}
int Tarjan(void)
{
    scc=dfn=stk[0]=0;
    _clr(cnc,0,MAXV);
    _clr(vis,false,MAXV);
    
    _for(i,0,n-1) if(!vis[i]) Tour(i);
    
    return scc;
}
#define _Recution
void redution(void)
{
    Q.clear();
    _clr(out,0,MAXV);
    _for(i,0,n-1) for(int j=pre[i];j!=-1;j=next[j])
    {
        if(cnc[i]!=cnc[G[j].v]) out[cnc[i]-1]++;
    }
    _for(i,0,scc-1) if(!out[i])
    {
        _for(j,0,n-1) if(cnc[j]-1==i)
        {
            Q.insert(j+1);
        }
    }
    if(!Q.empty())
    {
        set<int>::iterator i=Q.begin();
        printf("%d",*i);
        for(i++;i!=Q.end();i++) printf(" %d",*i);
    }
    printf("\n");
}
int main()
{
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        clear();
        _for(i,0,m-1)
        {
            scanf("%d %d",&u,&v);
            add(u-1,v-1,1);
        }
        Tarjan();
        redution();
    }
    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