PageRankLab2

#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;
#define MATRIX vector<vector<double> >
#define MAXN 5050
#define alpha 0.85
#define eps 1e-7
using namespace std;
//теория http://pidruchniki.com/71830/informatika/algoritm_pagerank
//http://www.cyberguru.ru/programming/programming-theory/matrix-vectors-values-page2.html
//http://info.alnam.ru/book_clm.php?id=64
int n , m; //n - cтраниц, m - ссылок
vi g[MAXN];
MATRIX H(MAXN , vector<double>(MAXN , 0.));
vector<bool> a(MAXN , 0);
MATRIX G(MAXN , vector<double>(MAXN , 0.));

inline double EuclideanNorm(vector<double> v){
    double sum = 0;
    rep(i , sz(v))sum += v[i] * v[i];
    return sqrt(sum);
}

inline double l_Norm(vector<double> v){
    double sum = 0;
    rep(i , n)sum += abs(v[i]);
    return sum;
}

inline vector<double> Substract(vector<double> & a , vector<double> & b){
    vector<double> res(n , 0.);
    rep(i , n)res[i] = a[i] - b[i];
    return res;
}

inline void Build_H(){
    rep(i , n){
        a[i] = !sz(g[i]);
        double cur = 1. / (double)sz(g[i]);
        for(int j : g[i]){
            H[i][j] = cur;
        }
    }
}

inline void Build_G(){
    rep(i , n){
        double t = (alpha * a[i] + (1 - alpha)) / (double)n;
        rep(j , n){
            G[i][j] = alpha * H[i][j];
            G[i][j] += t;
        }
    }
}

inline void Transpose(MATRIX & A){
    rep(i , n){
        repf(j , i + 1 , n){
            swap(A[i][j] , A[j][i]);
        }
    }
}

inline vector<double> MultV(MATRIX A , vector<double> v){
    vector<double> ans(sz(v) , 0);
    rep(i , sz(v)){
        rep(j , sz(v)){
            ans[i] += A[i][j] * v[j];
        }
    }
    return ans;
}

inline vector<double> Step(MATRIX G){
    vector<double> X(n , 1);
    vector<double> Y(n , 1);
    double cur_lambda1 , cur_lambda2 = INF;
    do{
        X = Y;
        cur_lambda1 = cur_lambda2;
        Y = MultV(G , Y);
        int pos = 0;
        while(abs(X[pos]) < eps)++pos;
        cur_lambda2 = Y[pos] / X[pos];
        double norm = l_Norm(Y);
        rep(i , n)Y[i] /= norm;

    }while(abs(cur_lambda1 - cur_lambda2) > eps);
    return X;
}

inline vector<double> PageRank(MATRIX G){
    Transpose(G);

//  rep(i , n)G[i][i] -= 1;
    vector<double> v = Step(G);//Gauss(G , vector<double>(n , 0.));
//  double norm = l_Norm(v);
//  rep(i , n)v[i] /= norm;
    return v;
}
/*
inline vector<double> Inverse_Iteration(MATRIX A){
    double lambda = 1;
    vector<double> X(MAXN , 1);
    vector<double> Y(MAXN , 1);
    rep(i , n){
        A[i][i] -= lambda;
    }
    int cnt = 0;
    do{
        X = Y;
        Y = Gauss(A , X);
        double norm = EuclideanNorm(Y);
        rep(i , n)Y[i] /= norm;
        rep(i , n)cout << Y[i] << " ";
        cout << nl;
    //  cout << "hi\n";
        if(++cnt > 100)break;
    }while(EuclideanNorm(Substract(X , Y)) > eps);
    return Y;
}*/

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(3);
    cout.setf(ios::fixed);
    cin >> n >> m;
    rep(i , m){
        int u , v;
        cin >> u >> v;
        --u;
        --v;
        g[u].pb(v);
    }
    Build_H();
    Build_G();
    rep(i , n){
        rep(j , n){
            cout << setw(4) << G[i][j] << " ";
        }
        cout << nl;
    }
    cout << nl;
    vector<double> v = PageRank(G);
    rep(i , n)cout << setw(4) << v[i] << " ";

    return 0;
}
/*
6 10
1 2
1 3
3 1
3 2
3 5
4 5
4 6
5 4
5 6
6 4
*/