AtCoder Beginner Contest 139 - E - League(グラフを使う)
グラフを使う版
DAGとして言い換えれる。
トポロジカルソートを実行して、できない場合は、-1
できるときは、最長がつまり日数になる
code: グラフ.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
typedef pair<int,int> P;
const int MAXN = 1005;
const int MAXV = MAXN*(MAXN-1)/2;
int toId(int i, int j) {
if (i > j) swap(i, j);
}
bool visitedMAXV; // 訪れたかのフラグ bool calculatedMAXV; // ループ検出用 int dpMAXV; // vからスタートした時の最長経路 int dfs(int v) {
// スタート地点に戻ってきてしまったら、ループなのでNG
if(!calculatedv) return -1; }
int res = dfs(u);
if(res == -1) return -1;
dpv = max(dpv, dfs(u)+1); }
}
int main() {
int n; cin >> n;
vector<vector<int>> a(n, vector<int>(n-1));
rep(i,n) rep(j,n-1) {
}
int V = 0;
rep(i, n) rep(j, n) {
if(i < j) idij = V++; // 頂点番号を割り当てる. }
rep(i, n) {
rep(j, n-1) {
}
rep(j, n-2) {
}
}
int ans = 0;
rep(i, V) {
int res = dfs(i);
if(res == -1) {
puts("-1");
return 0;
}
ans = max(ans, res);
}
cout << ans << endl;
return 0;
}