[ZJOI2007]最大半连通子图

Time Limit:30000MS  Memory Limit:165536K
Total Submit:45 Accepted:14
Case Time Limit:3000MS

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

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

Source

爆栈你二大爷啊！！
我晕。搞了半天WA意思就是爆栈啊。。这下没办法了。我弄了数据发现有一个点无论怎么搞都爆栈，C++又不像Pascal能调栈的，难不成自己写一个模拟版dfs囧囧，就这样吧。不去A这题了。。
这道题很明显要强联通缩点，我用的是Tarjan，然后很明显就变成了TAG上的最长路问题，可以DP解决。。
Code（爆栈一个点。我也没办法囧）：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<set>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000;
int n,m,mod;
vector<int> E[maxn];
typedef vector<int>::iterator it;
int ord[maxn]={0},low[maxn],stack[maxn],top=0,cnt=0,id[maxn],snt=0;
bool inStack[maxn]={0};
void dfs(int x)
{
ord[x]=low[x]=++cnt;
stack[top++]=x;inStack[x]=true;
for(it i=E[x].begin();i!=E[x].end();++i)
if(!ord[*i])
dfs(*i),low[x]=min(low[x],low[*i]);
else if(inStack[*i])
low[x]=min(low[x],ord[*i]);
if(low[x]==ord[x])
{
int u;do{u=stack[–top];id[u]=snt;inStack[u]=false;}while(u!=x);
snt++;
}
}
struct State
{
int Ans,Num;
State():Ans(0),Num(1){}
void Renew(const State&o)
{
if(o.Ans<Ans)return;
if(o.Ans>Ans){*this=o;return;}
Num+=o.Num;Num%=mod;
}
};
State Dp[maxn];
set<int> Edge[maxn];
typedef set<int>::iterator sit;
int In[maxn]={0},Num[maxn]={0};
int main()
{
//freopen("in","r",stdin);
scanf("%d %d %d",&n,&m,&mod);int s,t;
while(m–)scanf("%d %d",&s,&t),E[s-1].pb(t-1);
rep(i,n)if(!ord[i])dfs(i);
rep(i,n)
{
int own=id[i];Num[own]++;
for(it e=E[i].begin();e!=E[i].end();++e)
if(id[*e]!=own)
Edge[own].insert(id[*e]);
}
rep(i,snt) for(sit e=Edge[i].begin();e!=Edge[i].end();++e) In[*e]++;
queue<int> Q;vector<int> S;
rep(i,snt) if(!In[i]) Q.push(i);
while(Q.size())
{
int t=Q.front();Q.pop();
S.push_back(t);
for(sit i=Edge[t].begin();i!=Edge[t].end();++i)
if(!–In[*i]) Q.push(*i);
}
for(vector<int>::reverse_iterator i=S.rbegin();i!=S.rend();++i)
{
for(sit e=Edge[*i].begin();e!=Edge[*i].end();++e)
Dp[*i].Renew(Dp[*e]);
Dp[*i].Ans+=Num[*i];
}
State Ans;
rep(i,snt) Ans.Renew(Dp[i]);
cout<<Ans.Ans<<endl;
cout<<Ans.Num<<endl;
}