C++14(g++5.4) 解法, 执行用时: 592ms, 内存消耗: 33904K, 提交时间: 2020-01-05 16:29:26

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;

int N, M, X;

vector<int> G[MAXN];
vector<int> rG[MAXN];
bool vis[MAXN];
int scc_cnt;
int scc[MAXN];
int sccSz[MAXN];
vector<int> path;

void dfs(int s) {
  // cout << "dfs " << s << endl;
  vis[s] = true;
  for (auto t: G[s]) if (!vis[t]) dfs(t);
  path.push_back(s);
}
void rdfs(int s) {
  // cout << "rdfs " << s << " " << scc_cnt << endl;
  scc[s] = scc_cnt;
  sccSz[scc_cnt]++;
  for (auto t: rG[s]) if (!scc[t]) rdfs(t);
}

void Kosaraju() {
  for (int i = 1; i <= N; i++) if (!vis[i]) dfs(i);
  reverse(path.begin(), path.end());
  for (int i: path) if (!scc[i]) scc_cnt++, rdfs(i);
}


vector<int> g[MAXN];
int indeg[MAXN];
int ways[MAXN]; 
int cnt[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> N >> M >> X;
  while (M--) {
    int a, b; cin >> a >> b;
    G[a].push_back(b);
    rG[b].push_back(a);
  }
  Kosaraju();
  // for (int s = 1; s <= N; s++) cout << scc[s] << " "; cout << endl;
  for (int s = 1; s <= N; s++) {
    for (auto t: G[s]) if (scc[s] != scc[t]) g[scc[s]].push_back(scc[t]);
  }
  for (int s = 1; s <= scc_cnt; s++) {
    sort(g[s].begin(), g[s].end());
    g[s].erase(unique(g[s].begin(), g[s].end()), g[s].end());
    for (auto t: g[s]) indeg[t]++;
  }
  queue<int> Q;
  for (int i = 1; i <= scc_cnt; i++) if (indeg[i] == 0) {
    Q.push(i); 
    cnt[i] = sccSz[i];
    ways[i] = 1;
  }
  while (!Q.empty()) {
    int s = Q.front(); Q.pop();
    for (auto t: g[s]) {
      if (cnt[t] < sccSz[t] + cnt[s]) {
        cnt[t] = sccSz[t] + cnt[s];
        ways[t] = ways[s]; 
      } else if (cnt[t] == sccSz[t] + cnt[s]) {
        ways[t] = (ways[t] + ways[s])%X;
      }
      if (--indeg[t] == 0) Q.push(t);
    }
  }
  int best_cnt = 0; 
  int best_ways = 0;
  for (int i = 1; i <= scc_cnt; i++) {
    if (best_cnt < cnt[i]) {
      best_cnt = cnt[i];
      best_ways = ways[i];
    } else if (best_cnt == cnt[i]) {
      best_ways = (best_ways + ways[i]) % X;
    }
  }
  cout << best_cnt << endl;
  cout << best_ways << endl; 
}

C++(clang++11) 解法, 执行用时: 356ms, 内存消耗: 49376K, 提交时间: 2020-11-25 20:47:46

#include<bits/stdc++.h>
#define ui unsigned int
#define ep emplace
#define epb emplace_back
using namespace std;
const int nn=101125;
bool in[nn];
int n,m,x,a,b,k[nn],c[nn];
int dfn[nn],com[nn],size[nn];
stack<int>st;
vector<int>t[nn];
set<int>ct[nn];
int tarjan(int u){
	int low;
	low=dfn[u]=++dfn[0];
	st.ep(u),in[u]=true;
	for(int v:t[u])
		if(dfn[v]){
			if(in[v])low=min(low,dfn[v]);
		}else low=min(low,tarjan(v));
	if(low==dfn[u]){
		in[u]=false,com[u]=++com[0];
		for(;st.top()!=u;st.pop())
			in[st.top()]=false,
			com[st.top()]=com[0];
		st.pop();
	}return low;
}int dfs(int u){
	if(k[u])return k[u];
	c[u]=1%x;
	for(int v:ct[u])
		if(k[u]<dfs(v)){
			k[u]=k[v],c[u]=c[v];
		}else if(k[u]==k[v]){
			c[u]=(c[u]+c[v])%x;
		}
	return k[u]+=size[u];
}int main(){
	scanf("%d%d%d",&n,&m,&x);
	while(m--)
		scanf("%d%d",&a,&b),
		t[a].epb(b);
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++){
		size[com[i]]++;
		for(int j:t[i])
			if(com[i]!=com[j])
				ct[com[i]].insert(com[j]);
	}
	for(int i=1;i<=com[0];i++)
		ct[0].insert(i);
	dfs(0),printf("%d\n%d",k[0],c[0]);
	return 0;
}