题目描述：

5000个点的有向图，保证任意两点间仅有一条有向边。

问有没有长度为3的环，有的话任意输出一个，SPJ。

没有的话，输出-1。

解题报告：

         增量算法，充分利用“任意两点间仅有一条有向边”的性质。

         假设前面已经加入了N个点，现在来了第N+1个点。

         那么一定能将N个点分成left和right两部分，使得N+1号点到left有边，right到N+1号点右边（因为任意两点间都有边），那么，如果left的任意一个点l到right任意一个点r有边的话，那么就有答案N+1->l->r->N+1这样一个长度为3的环。

         那么每次加入N+1号点后，用O(N)的复杂度求出左边的数量leftnum，右边的数量rightnum，left的出度和leftout，left的入度和leftin。

         如果left没有一条到right的边，则一定满足：

         leftin = leftout + leftnum * rightnum（left和right任意两点右边，如果没有左到右的，那么leftnum*rightnum条边都是右到左的）

         那么，如果leftin != leftout + leftnum * rightnum，则暴力枚举左点，右点即可得到答案。

         总体复杂度O(n^2)

代码如下：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

#include<cstdio>

using namespace std;

#define SIZE 6000

char g[SIZE][SIZE];

int n, rd[SIZE], cd[SIZE];

int main()

{

    scanf("%d", &n);

    bool flag = false;

    for(int i = 0; i < n; i++) scanf("%s", g[i]);

    for(int i = 0; i < n; i++)

    {

        int leftin = 0, leftout = 0, leftnum = 0;

        for(int j = 0; j < i; j++)

            if (g[i][j] == '1')

                leftin += rd[j], leftout += cd[j], leftnum++;

        if (leftin != leftout + leftnum * (i - leftnum))

        {

            for(int left = 0; left < i && !flag; left++) if (g[i][left] == '1')

                for(int right = 0; right < i && !flag; right++) if (g[left][right] == '1' && g[right][i] == '1')

                {

                    flag = true;

                    printf("%d %d %d\n", i + 1, left + 1, right + 1);

                    goto lable;

                }

        }

        for(int j = 0; j < i; j++)

        {

            if (g[i][j] == '1') rd[j]++, cd[i]++;

            if (g[j][i] == '1') cd[j]++, rd[i]++;

        }

    }

    lable:

    if (!flag) printf("-1\n");

         return 0;

}