【BZOJ】1093: [ZJOI2007]最大半连通子图（tarjan+拓扑序）-白红宇

【BZOJ】1093: [ZJOI2007]最大半连通子图（tarjan+拓扑序）

阅读量：6271 次

发布时间：2019-06-22

本文共 1684 字，大约阅读时间需要 5 分钟。

两个条件综合起来加上求最大的节点数，那么很明显如果是环一定要缩点。

然后再仔细思考下就是求dag的最长路的数目啦。。。

然后wa了。。。

看了题解。。。噗！第一次注意到缩点后会有重边QAQ。。。于是。。

orz orz

然后思考了下怎么处理重边。。。很简单，每个点bfs时记录一下就行了。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef long long ll;#define pii pair
              
               #define mkpii make_pair
               
                #define pdi pair
                
                 #define mkpdi make_pair
                 
                  #define pli pair
                  
                   #define mkpli make_pair
                   
                    #define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a

Description

Input

第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。

Output

应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

Sample Input

6 6 20070603

1 2

2 1

1 3

2 4

5 6

6 4

Sample Output

HINT

对于100%的数据， N ≤100000, M ≤1000000；对于100%的数据， X ≤10^8。

Source

转载地址：http://ailpa.baihongyu.com/

你可能感兴趣的文章