Cod sursa(job #2822347)

Utilizator Angel2IonitaAngel Ionita Angel2Ionita Data 23 decembrie 2021 21:03:58
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 18.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <climits>

using namespace std;

ifstream f("darb.in");
ofstream o("darb.out");

class Graph
{
    const int INF= INT_MAX;
    void DFS(int node, vector<bool> &vis)
    {
        vis[node] = true;
        for (auto i : adjList[node])
            if (!vis[i])
                DFS(i, vis);
    }
    void DFS1(int node, vector<bool> &vis, stack<int> &S)
    {
        vis[node] = true;
        for (auto i : adjList[node])
            if (!vis[i])
                DFS1(i, vis, S);
        S.push(node);
    }
    void DFS2(int node, vector<bool> &vis, vector<vector<int>> &scc, int it)
    {
        vis[node] = true;
        scc[it].push_back(node);
        for (auto i : adjList[node])
            if (!vis[i])
                DFS2(i, vis, scc, it);
    }
    void DFS_sortaret(int node, vector<bool> &vis, stack<int> &S)
    {
        vis[node] = true;
        for (auto i : adjList[node])
            if (!vis[i])
                DFS_sortaret(i, vis, S);
        S.push(node);
    }
    Graph TransposeGraph()
    {
        Graph Tg(size,false);
        for (int i = 0; i < size; i++)
            for (auto j : adjList[i])
                Tg.adjList[j].push_back(i);
        return Tg;
    }
    void dfs_base(int node, int k, bool visited[], int &diameter,int &fnode)
    {
        visited[node] = true;
        k++;
        for (auto i : adjList[node])
        {
            if (!visited[i])
            {
                if (k >= diameter)
                {
                    diameter = k;
                    fnode = i;
                }
                dfs_base(i, k, visited, diameter,fnode);
            }
        }
    }
    void dfs_darb(int node, int &diameter,int &fnode)
    {
        bool *visited = new bool[size];
        int k = 0;
        for (int i = 0; i < size; i++)
            visited[i] = false;
        dfs_base(node, k + 1, visited, diameter,fnode);
    }
    bool hk_bfs(vector<int> &toRight, vector<int> &toLeft, vector<int> &dist)
    {
        queue<int> q;
        for (int u = 1; u <= size; u++)
        {
            if (toRight[u] == 0)
            {

                dist[u] = 0;
                q.push(u);
            }
            else
                dist[u] = INF;
        }
        dist[0] = INF;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            if (dist[u] < dist[0])
            {
                for (auto i:adjList[u])
                {
                    int v = i;
                    if (dist[toLeft[v]] == INF)
                    {
                        dist[toLeft[v]] = dist[u] + 1;
                        q.push(toLeft[v]);
                    }
                }
            }
        }
        return (dist[0] != INF);
    }
    bool hk_dfs(int u, vector<int> &toRight, vector<int> &toLeft, vector<int> &dist)
    {
        if (u != 0)
        {
            for (auto i : adjList[u])
            {
                int v = i;
                if (dist[toLeft[v]] == dist[u] + 1)
                {
                    if (hk_dfs(toLeft[v], toRight, toLeft, dist) == true)
                    {
                        toLeft[v] = u;
                        toRight[u] = v;

                        return true;
                    }
                }
            }
            dist[u] = INF;
            return false;
        }
        return true;
    }
public:
    vector<vector<int>> adjList;
    vector<vector<pair<int, int>>> adjListW;
    int size,size2;
    Graph(int n,bool isWeighted)
    {
        size = n;
        //true for weighted graph , false for unweighted graph
        if(isWeighted) 
            adjListW.resize(size);
        else
            adjList.resize(size);
    }
    Graph(int n,int m,bool option)
    {
        size = n;
        size2 = m;
        //true for maximum bipartite matching , false for eulerian cycle
        if(option) 
            adjList.resize(size+1); 
        else
            adjList.resize(size);
    }
    void addEdgeD(int start, int end)
    {
        adjList[start].push_back(end);
    }
    void addEdgeU(int start, int end)
    {
        adjList[start].push_back(end);
        adjList[end].push_back(start);
    }
    void addEdgeDW(int start, int end, int weight)
	{
		adjListW[start].push_back(make_pair(end, weight));
	}
	void addEdgeUW(int start, int end, int weight)
	{
		adjListW[start].push_back(make_pair(end, weight));
		adjListW[end].push_back(make_pair(start, weight));
	}
    void addEdgeMultigraph(int start, int end, int i, vector<int> &source, vector<int> &destination)
    {
        adjList[start].push_back(i);
        adjList[end].push_back(i);
        source.push_back(start);
        destination.push_back(end);
    }
    vector<int> BFS(int node) //BFS
    {
        vector<int> Cost;
        queue<int> Q;
        for (int i = 0; i < size; i++)
            Cost.push_back(-1);
        Cost[node] = 0;
        Q.push(node);
        while (!Q.empty())
        {
            node = Q.front();
            Q.pop();
            for (auto i : adjList[node])
                if (Cost[i] == -1)
                {
                    Cost[i] = Cost[node] + 1;
                    Q.push(i);
                }
        }
        return Cost;
    }
    int Connected() //DFS
    {
        vector<bool> vis;
        for (int i = 0; i < size; i++)
            vis.push_back(false);
        int k = 0;
        for (int i = 0; i < size; i++)
            if (!vis[i])
            {
                DFS(i, vis);
                k++;
            }
        return k;
    }
    pair<int,vector<vector<int>>> SCC() //ctc
    {
        int it = 0;
        vector<vector<int>> scc;
        stack<int> S;
        vector<bool> vis;
        for (int i = 0; i < size; i++)
            vis.push_back(false);
        for (int i = 0; i < size; i++)
            if (!vis[i])
                DFS1(i, vis, S);
        Graph Tg = TransposeGraph();
        for (int i = 0; i < size; i++)
            vis[i] = false;
        while (!S.empty())
        {
            int node = S.top();
            S.pop();
            if (!vis[node])
            {
                scc.resize(it + 1);
                Tg.DFS2(node, vis, scc, it);
                it++;
            }
        }
        /*for (int i = 0; i < scc.size(); i++)
            for (int j = 0; j < scc[i].size(); j++)
                scc[i][j]++;*/
        return {it,scc};
        /*o << it << endl;
        for (int i = 0; i < scc.size(); i++)
        {
            for (int j = 0; j < scc[i].size(); j++)
                o << scc[i][j] + 1 << " ";
            o << endl;
        }*/

    }
    vector<int> tS() //sortaret
    {
        vector<int> res;
        stack<int> S;
        vector<bool> vis;
        for (int i = 0; i < size; i++)
            vis.push_back(false);
        for (int i = 0; i < size; i++)
            if (!vis[i])
                DFS_sortaret(i, vis, S);
        while (!S.empty())
        /*{
            o << S.top() + 1 << " ";
            S.pop();
        }*/
        {
            res.push_back(S.top()+1);
            S.pop();
        }
        return res;
    }
    vector<pair<int,int>> MST() //apm
	{
		vector<pair<int,int>> res;
        int Tcost = 0, src = 0;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		vector<int> parent(size, -1);
		vector<int> cost(size, INF);
		vector<bool> inMST(size, false);
		pq.push(make_pair(0, src));
		cost[src] = 0;
		while (!pq.empty())
		{
			int u = pq.top().second;
			pq.pop();
			if (!inMST[u])
			{
				inMST[u] = true;
				for (auto i : adjListW[u])
				{
					int v = i.first;
					int weight = i.second;
					if (!inMST[v] && cost[v] > weight)
					{
						cost[v] = weight;
						pq.push(make_pair(cost[v], v));
						parent[v] = u;
					}
				}
			}
		}
		for (auto elem : cost)
			Tcost += elem;
        res.push_back(make_pair(Tcost,size-1));
        for (int i = 1; i < size; i++)
            res.push_back(make_pair(parent[i]+1,i+1));
        return res;
	}
	vector<int> Dijkstra() //dijkstra
	{
		int src = 0;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		vector<int> dist(size, INF);
		pq.push(make_pair(0, src));
		dist[src] = 0;
		while (!pq.empty())
		{
			int u = pq.top().second;
			pq.pop();
			for (auto i : adjListW[u])
			{
				int v = i.first;
				int weight = i.second;
				if (dist[v] > dist[u] + weight)
				{
					dist[v] = dist[u] + weight;
					pq.push(make_pair(dist[v], v));
				}
			}
		}
        for (int i = 1; i < size; i++)
			if (dist[i] == INF)
				dist[i]=0;
        return dist;
	}
	vector<int> BellmanFord()   //bellman-ford
	{
		int src = 0;
		vector<bool> inq(size, false);
		vector<int> dist(size, INF);
		dist[src] = 0;
		queue<int> q;
		vector<int> count_q(size,0);
		q.push(src);
		inq[0] = true;
		while (!q.empty())
		{
			int v = q.front();
			q.pop();
			inq[v] = false;
			for (auto pr : adjListW[v])
			{
				int u = pr.first;
				int weight = pr.second;
				if (dist[v] != INF && dist[u] > dist[v] + weight)
				{
					dist[u] = dist[v] + weight;
					if (!inq[u])
					{
						if(count_q[u]>size)
							{
								//o<<"Ciclu negativ!";
                                dist.clear();
								return dist;
							}
						else
						{
							q.push(u);
							inq[u]=true;
							count_q[u]++;

						}

					}
				}
			}
		}
		/*for (int i = 1; i < size; i++)
			if (dist[i] != INF)
				o << dist[i] << " ";
			else
				o << 0 << " ";*/
        for (int i = 1; i < size; i++)
			if (dist[i] == INF)
				dist[i]=0;
        return dist;
	}
    int diameter() //diametru
    {
        int fnode;
        int diameter = -1;
        dfs_darb(0, diameter,fnode);
        dfs_darb(fnode, diameter,fnode);
        return diameter;
    }
    vector<int> eulerian_cycle(vector<int> &source, vector<int> &destination) //ciclueuler
    {
        vector<int> result;
        vector<bool> usedEdge(size2, false);
        stack<int> st;
        for (int i = 0; i < size; i++)
        {
            if (adjList[i].size() % 2 == 1)
            {
                result.push_back(-1);
                return result;
            }
        }
        st.push(0);
        while (!st.empty())
        {
            int node = st.top();
            if (!adjList[node].empty())
            {
                int e = adjList[node].back();
                adjList[node].pop_back();
                if (!usedEdge[e])
                {
                    usedEdge[e] = true;
                    int to = source[e] ^ destination[e] ^ node;
                    st.push(to);
                }
            }
            else
            {
                st.pop();
                result.push_back(node + 1);
            }
        }
        return result;
    } 
    pair<int, vector<int>> HopcroftKarp(vector<int> &toRight, vector<int> &toLeft, vector<int> &dist) //cuplaj
    {
        dist.resize(size + 1);
        for (int u = 0; u <= size; u++)
            toRight.push_back(0);
        for (int v = 0; v <= size2; v++)
            toLeft.push_back(0);

        int count = 0;

        while (hk_bfs(toRight, toLeft, dist))
        {
            for (int u = 1; u <= size; u++)
                if (toRight[u] == 0 && hk_dfs(u, toRight, toLeft, dist))
                    count++;
        }
        return {count, toRight};
    }
};
bool graphExists(vector<int> &v)
{
    while (1)
    {
        sort(v.begin(), v.end(), greater<>());
        if (!v[0])
            return true;
        int s = v[0];
        v.erase(v.begin());
        if (s > v.size())
            return false;
        for (int i = 0; i < s; i++)
        {
            v[i]--;
            if (v[i] < 0)
                return false;
        }
    }
}
class DisjointSets
{
    int size,*rank,*parent;
public:
    DisjointSets(int n)
    {
        size = n + 1;
        rank=new int[size];
        parent=new int[size];
        for (int i = 1; i < size; i++)
        {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    int Find(int x)
    {
        if (parent[x] == x)
            return x;
        return Find(parent[x]);
    }

    void Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if (rank[fx] <= rank[fy])
        {
            parent[fx] = fy;
            rank[fy] += rank[fx];
        }
        else
        {
            parent[fy] = fx;
            rank[fx] += rank[fy];
        }
    }
    ~DisjointSets()
    {
        delete[] parent;
        delete[] rank;
    }
};
class RoyFloydG
{
    int size;

public:
    int **matrix;
    RoyFloydG(int n)
    {
        size = n;
        matrix = new int *[size];
        for (int i = 0; i < size; i++)
            matrix[i] = new int[size];
    }
    void RoyFloyd()
    {
        int i, j, k;
        for (k = 0; k < size; k++)
            for (i = 0; i < size; i++)
                for (j = 0; j < size; j++)
                    if (matrix[i][k] && matrix[k][j] && (matrix[i][j] > matrix[i][k] + matrix[k][j] || !matrix[i][j]) && i != j)
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
    }

    ~RoyFloydG()
    {
        for (int i = 0; i < size; i++)
            delete[] matrix[i];
        delete[] matrix;
    }
};
void Solve_BFS()
{
    int n, m, s;
    int x, y;
    f >> n >> m >> s;
    Graph g(n,false);
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        g.addEdgeD(x - 1, y - 1);
    }
    vector<int> res=g.BFS(s - 1);
    for(auto elem:res)
        o<<elem<<" ";
}
void Solve_DFS()
{
    int n, m;
    int x, y;
    f >> n >> m;
    Graph g(n,false);
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        g.addEdgeU(x-1, y-1);
    }
    o << g.Connected();
}
void Solve_CTC()
{
    int n, m;
    int x, y;
    f >> n >> m;
    Graph g(n,false);
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        g.addEdgeD(x - 1, y - 1);
    }
    pair<int,vector<vector<int>>> res=g.SCC();
    o << res.first << endl;
    for (int i = 0; i < res.second.size(); i++)
    {
        for (int j = 0; j < res.second[i].size(); j++)
            o << res.second[i][j] + 1 << " ";
        o << endl;
    }
}
void Solve_sortaret()
{
    int n, m;
    int x, y;
    f >> n >> m;
    Graph g(n,false);
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        g.addEdgeD(x - 1, y - 1);
    }
    vector<int> res=g.tS();
    for(auto elem:res)
        o<<elem<<" ";
}
void Solve_Havel_Hakimi()
{
    int n, x;
    vector<int> v;
    f >> n;
    for (int i = 0; i < n; i++)
    {
        f >> x;
        v.push_back(x);
    }
    if (graphExists(v))
        cout << "Da";
    else
        cout << "Nu";
}
void Solve_APM(){
    int N, M;
	int x, y, w;
	f >> N >> M;
	Graph g(N,true);
	for (int i = 1; i <= M; i++)
	{
		f >> x >> y >> w;
		g.addEdgeUW(x - 1, y - 1, w);
	}
    vector<pair<int,int>> res=g.MST();
    o<<res[0].first<<endl;
    o<<res[0].second<<endl;
    for(int i=1;i<res.size();i++)
        o<<res[i].first<<" "<<res[i].second<<endl;
}
void Solve_Dijkstra(){
    int N, M;
	int x, y, w;
	f >> N >> M;
	Graph g(N,true);
	for (int i = 1; i <= M; i++)
	{
		f >> x >> y >> w;
		g.addEdgeDW(x - 1, y - 1, w);
	}
    vector<int> res=g.Dijkstra();
    for(int i=1;i<res.size();i++)
        o<<res[i]<<" ";
}
void Solve_BellmanFord(){
    int N, M;
	int x, y, w;
	f >> N >> M;
	Graph g(N,true);
	for (int i = 1; i <= M; i++)
	{
		f >> x >> y >> w;
		g.addEdgeDW(x - 1, y - 1, w);
	}
    vector<int> res=g.BellmanFord();
    if(res.empty())
        o<<"Ciclu negativ!";
    else
        for(int i=1;i<res.size();i++)
            o<<res[i]<<" ";
}
void Solve_disjoint(){
    int N, M;
    int cod, x, y;
    f >> N >> M;
    DisjointSets ds(N);
    for (int i = 1; i <= M; i++)
    {
        f >> cod >> x >> y;
        if (cod == 1)
            ds.Union(x, y);
        else if (ds.Find(x) == ds.Find(y))
            o << "DA\n";
        else
            o << "NU\n";
    }
}
void Solve_darb(){
    int N, x, y;
    f >> N;
    Graph g(N,false);
    for (int i = 1; i <= N - 1; i++)
    {
        f >> x >> y;
        g.addEdgeU(x - 1, y - 1);
    }
    o << g.diameter();
}
void Solve_royfloyd(){
    int N;
    f >> N;
    RoyFloydG g(N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            f >> g.matrix[i][j];
    g.RoyFloyd();
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            o << g.matrix[i][j] << " ";
        o << endl;
    }
}
void Solve_ciclueuler()
{
    vector<int> source, destination;
    int N, M, x, y;
    f >> N >> M;
    Graph g(N, M,false);
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        g.addEdgeMultigraph(x - 1, y - 1, i, source, destination);
    }
    vector<int> result = g.eulerian_cycle(source, destination);
    if (result[0] == -1)
        o << -1;
    else
        for (int i = 0; i < M; i++)
            o << result[i] << ' ';
}
void Solve_cuplaj()
{
    int N, M, E;
    f >> N >> M >> E;
    Graph g(N, M,true);
    int x, y;
    for (int i = 1; i <= E; i++)
    {
        f >> x >> y;
        g.addEdgeD(x, y);
    }
    vector<int> toRight, toLeft, dist;
    pair<int, vector<int>> res = g.HopcroftKarp(toRight, toLeft, dist);
    o << res.first << endl;
    for (int i = 1; i <= N; i++)
        if (res.second[i])
            o << i << " " << res.second[i] << endl;
}
int main()
{
    //Solve_BFS();            
    //Solve_DFS();            
    //Solve_CTC();            
    //Solve_sortaret();       
    //Solve_Havel_Hakimi();   

    //Solve_APM();             
    //Solve_Dijkstra();       
    //Solve_BellmanFord();    
    //Solve_disjoint();       

    Solve_darb();           
    //Solve_royfloyd();       

    //Solve_ciclueuler();     
    //Solve_cuplaj();         
    
    return 0;
}