Submission #1646654

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 1005, MOD = 1000000007;
typedef long long i64;
typedef pair<int, int> pii;

class Edge {
public:
  int nxt, to;
} e[MAX_N << 1];

int head[MAX_N], cnt, C[MAX_N][MAX_N];
void addedge(int u, int v) {
  e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}

int N, M, K, dfn[MAX_N], low[MAX_N], dfs_clock;
int st[MAX_N], top, bcc_cnt;

vector<int> block[MAX_N];

pii edge[MAX_N];

void find_bcc(int u, int v) {
  dfn[u] = ++dfs_clock, low[u] = dfn[u];

  int temp;
  
  for (int i = head[u]; i; i = e[i].nxt) 
    if (!dfn[e[i].to]) {
      temp = top, st[++top] = (i + 1) / 2;
      find_bcc(e[i].to, u), low[u] = min(low[u], low[e[i].to]);

      if (low[e[i].to] >= dfn[u]) {
	++bcc_cnt;
	while (top > temp) block[bcc_cnt].push_back(st[top--]);
      }
      
    } else if (e[i].to != v && dfn[e[i].to] < dfn[u]) {
      low[u] = min(low[u], dfn[e[i].to]);
      st[++top] = (i + 1) / 2;
    }
}

int fa[MAX_N];
int find(int x) {
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}

i64 fpm(i64 x, i64 y) {
  i64 res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return res;
}

i64 work(vector<int> &v) {
  for (int i = 1; i <= N; ++i) fa[i] = i;

  int num = 0, n = v.size();
  for (int x : v) {
    int u = find(edge[x].first), v = find(edge[x].second);
    if (u == v) num++;
    else fa[u] = v;
  }

  if (num == 0) return K;
  else if (num == 1) {
    i64 res = 0;
    for (int i = 1; i <= n; ++i)
      res = (res + fpm(K, __gcd(i, n))) % MOD;
    res = res * fpm(n, MOD - 2) % MOD;
    return res;
  } else {
    return C[n + K - 1][K - 1];
  }
  
}

int main() {

  scanf("%d%d%d", &N, &M, &K);

  for (int i = 0; i < MAX_N; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
  
  for (int i = 1, u, v; i <= M; ++i) {
    scanf("%d%d", &u, &v);
    addedge(u, v);
    edge[i] = make_pair(u, v);
  }

  for (int i = 1; i <= N; ++i)
    if (!dfn[i]) find_bcc(i, 0);

  i64 res = 1;
  for (int i = 1; i <= bcc_cnt; ++i)
    res = res * work(block[i]) % MOD;

  printf("%lld\n", res);
  
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:90:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &N, &M, &K);
                              ^
./Main.cpp:99:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &u, &v);
                          ^

Judge Result