1738 - TWO NODES

时间限制:	10000 MS
内存限制:	65535 KB

问题描述

Suppose that G is an undirected graph, and the value of stab is defined as follows:

Among the expression, G_-i,-j is the remainder after removing node i, node j and all edges that are directly relevant to the previous two nodes.cntCompent(X) is the number of connected components of X independently.

Thus, given a certain undirected graph G, you are supposed to calculating the value of stab .

输入说明

Input consists of multiple cases.

The input will contain the description of several graphs. For each graph, the description consist of an integer N for the number of nodes, an integer M for the number of edges, and M pairs of integers for edges (3<=N,M<=5000).

Please note that the endpoints of edge is marked in the range of [0,N-1], and input cases ends with EOF.

输出说明

For each graph in the input, you should output the value of stab.

输入样例

4 50 11 22 33 00 2

输出样例

来源

2013 ACM-ICPC China Nanjing Invitational Programming Contest

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#pragma comment(linker, "/STACK:10240000000000,10240000000000")using namespace std;typedef long long LL ;const int Max_N=5008 ;struct Edge{ int v ; int next ;};Edge edge[Max_N*2] ;int id ,indx ;int vec[Max_N] ,dfn[Max_N] ,low[Max_N] ;bool visited[Max_N];void add_edge(int u ,int v){ edge[id].v=v ; edge[id].next=vec[u] ; vec[u]=id++ ;}void init(){ id=0 ; indx=0 ; memset(vec,-1,sizeof(vec)) ;}int ans ,root_son ;int can_use[Max_N] ;void dfs(int u ,bool is_root){ dfn[u]=low[u]=++indx ; visited[u]=1 ; int child = 0 ; for(int e=vec[u];e!=-1;e=edge[e].next){ int v=edge[e].v ; if(can_use[v]==0) continue ; if(!dfn[v]){ dfs(v,0) ; if(is_root) root_son++ ; else{ low[u]=Min(low[u],low[v]) ; if(low[v]>=dfn[u]) child++ ; } } else low[u]=Min(low[u],dfn[v]) ; } ans=Max(ans ,child+1) ; //注意+1}int tarjan(int root){ if(vec[root]==-1) //块内就一个点的情况 return 0 ; memset(dfn,0,sizeof(dfn)) ; ans=0 ; //删除当前块里面的某点产生的分量数 root_son=0 ; dfs(root,1) ; ans=Max(ans,root_son) ; return ans ;}int main(){ int N ,M ,u ,v ,ans ,child ,sum; while(scanf("%d%d",&N,&M)!=EOF){ init() ; sum=0 ; while(M--){ scanf("%d%d",&u,&v) ; add_edge(u,v) ; add_edge(v,u) ; } memset(can_use,1,sizeof(can_use)) ; for(int k=0;k

转载于:https://www.cnblogs.com/liyangtianmen/p/3397703.html

你可能感兴趣的文章