tarjan+dp

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 #define rep(i,l,r) for(int i=l;i<(r);i++) 12 #define clr(a,x) memset(a,x,sizeof(a)) 13 using namespace std; 14 typedef long long ll; 15 typedef pair
                
                  pii; 16 #define mkp(a,b) make_pair(a,b) 17 int readint(){ 18 int ans=0,f=1; 19 char c=getchar(); 20 while(!isdigit(c)){ 21 if(c=='-') f=-1; 22 c=getchar(); 23 } 24 while(isdigit(c)){ 25 ans=ans*10+c-'0'; 26 c=getchar(); 27 } 28 return ans*f; 29 } 30 const int maxn=100009,maxm=1000009; 31 int n,m,mod,dfstime,scccnt,l[maxn],cnt[maxn],s[maxn],scc[maxn],low[maxn],pre[maxn]; 32 bool p[maxn]; 33 set
                 
                  Set; 34 struct edge{ 35 int v; 36 edge*next; 37 }e[maxm],*fir[maxn],*cur[maxn],*pt=e,E[maxm],*Fir[maxn],*Cur[maxn],*Pt=E; 38 void addedge(int u,int v){ 39 pt->v=v;if(!fir[u]) fir[u]=pt; 40 if(cur[u]) cur[u]->next=pt; 41 cur[u]=pt;pt++; 42 } 43 void Addedge(int u,int v){ 44 Pt->v=v;if(!Fir[u]) Fir[u]=Pt; 45 if(Cur[u]) Cur[u]->next=Pt; 46 Cur[u]=Pt;Pt++; 47 } 48 stack
                  
                   S; 49 void dfs(int x){ 50 S.push(x); 51 low[x]=pre[x]=++dfstime; 52 for(edge*e=fir[x];e;e=e->next){ 53 if(!pre[e->v]){ 54 dfs(e->v); 55 low[x]=min(low[x],low[e->v]); 56 }else if(!scc[e->v]) low[x]=min(low[x],pre[e->v]); 57 } 58 if(low[x]==pre[x]){ 59 int k=0;++scccnt; 60 while(k!=x){ 61 k=S.top();S.pop(); 62 scc[k]=scccnt; 63 s[scccnt]++; 64 } 65 } 66 } 67 void tarjan(){ 68 rep(i,1,n+1) if(!scc[i]) dfs(i); 69 } 70 void dp(int x){ 71 if(p[x]) return; 72 p[x]=1; 73 for(edge*e=Fir[x];e;e=e->next){ 74 dp(e->v); 75 if(l[e->v]>l[x]){ 76 l[x]=l[e->v];cnt[x]=cnt[e->v]%mod; 77 }else if(l[e->v]==l[x]) cnt[x]=(cnt[x]+cnt[e->v])%mod; 78 } 79 if(!cnt[x]) cnt[x]=1;l[x]+=s[x]; 80 } 81 int main(){ 82 cin>>n>>m>>mod; 83 rep(i,1,m+1){ 84 int from=readint(),to=readint(); 85 addedge(from,to); 86 } 87 tarjan(); 88 rep(i,1,n+1){ 89 for(edge*e=fir[i];e;e=e->next){ 90 if(scc[i]!=scc[e->v]&&Set.find(mkp(scc[i],scc[e->v]))==Set.end()){ 91 Addedge(scc[i],scc[e->v]); 92 Set.insert(mkp(scc[i],scc[e->v])); 93 } 94 } 95 } 96 rep(i,1,scccnt+1) if(!p[i]) dp(i); 97 int maxl=0,maxcnt=0; 98 rep(i,1,scccnt+1){ 99 if(l[i]>maxl){100 maxl=l[i];maxcnt=cnt[i];101 }else if(l[i]==maxl) maxcnt=(maxcnt+cnt[i])%mod;102 }103 printf("%d\n%d\n",maxl,maxcnt);104 return 0;105 }
                  
                 
                
               
              
             
            
           
          
         
        
       
      

1093: [ZJOI2007]最大半连通子图

Time Limit: 30 Sec  Memory Limit: 162 MB

Submit: 2215  Solved: 874

[][][]

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

3

3

HINT

 

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

 

Source

 

[ ][ ][ ]