(LightOj) 1291 – Real Life Traffic

/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here


#define MAXX 10007

vector<int>graph[MAXX];
int n, m;
map<int, map<int, int> > isBridge;




bool visited[MAXX];
int low[MAXX], disc[MAXX];
int parent[MAXX];

int t;
vector<paii>bridges;

int cnt[MAXX];

void dfs_bridge(int u)
{
	visited[u] = true;

	low[u] = disc[u] = ++t;

	loop(i, SZ(graph[u]))
	{
		int v = graph[u][i];

		if( ! visited[v])
		{
			parent[v] = u;

			dfs_bridge(v);

			low[u] = min(low[u], low[v]);

			if(low[v] > disc[u] )
			{
				bridges.pb(MP(u, v));

				isBridge[u][v] = isBridge[v][u] = 1;
			}
		}
		else if( v != parent[u])
		{
			low[u] = min(low[u], disc[v]);
		}
	}

}


int find(int u)
{
	if(u == parent[u]) return u;
	else return parent[u] = find(parent[u]);
}







int main()
{
	int kases, kaseno = 0;

	take(kases);

	while(kases--)
	{
		loop(i, MAXX) graph[i].clear();
		
		isBridge.clear();



		take(n, m);

		int u, v;

		loop(i, m)
		{
			take(u, v);

			graph[u].pb(v);
			graph[v].pb(u);
		}


		mem(visited, 0);
		mem(parent, -1);

		t = 0;
		bridges.clear();

		loop(i, n)
		{
			if(!visited[i])
			{
				dfs_bridge(i);
			}
		}

		loop(i, n)
		{
			parent[i] = i;
		}


		loop(i, n)
		{
			loop(j, SZ(graph[i]))
			{
				int v = graph[i][j];

				if(isBridge[i][v] != 1)
				{
					//cerr<<"i is "<<i<<" and v  = "<<v<<"   "<<isBridge[u][v]<<endl;
					
					int u = find(i);

					v = find(v);


					if( u != v)
					{
						parent[u] = v;

						//cerr<<"connecting "<<u<<" and "<<v<<endl;
					}
				}
				else
				{
					//dump(u); dump(v);
					//cerr<<"here"<<endl;
				}
				
			}
		}

		mem(cnt, 0);
		
		loop(i, SZ(bridges))
		{
			int u = bridges[i].fr, v = bridges[i].sc;

			u = find(u);

			v = find(v);


			//dump(u); dump(v);

			cnt[u]++;
			cnt[v]++;
		}


		int ret = 0;

		loop(i, n)
		{
			if(cnt[i] == 1)
			{
				ret++;
			}
		}


		//ret = count of leaf

		ret = (ret + 1)/2;






		pf("Case %d: %d\n", ++kaseno, ret);
	}



}

(UVa) 459 – Graph Connectivity

/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=400
*/

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>



#include<string>
#include<vector>
#include<map>
#include<queue>
#include<stack>


#define loop(i, n) for(int i=0; i<n; i++)
#define loopfrom1(i, n) for(int i=1; i<n; i++)
#define mem(array, value) memset(array, value, sizeof(array))
#define MIN(a, b) (a<b?a:b)
#define MAX(a, b) (a>b?a:b)
#define pb(a) push_back(a)
#define SZ size()
#define getint(n) scanf("%d", &n)
#define pi acos(-1.0)
#define inf 536870912         // 1<<29
#define debug cout<<"ok"<<endl
#define ll long long int
#define mod(a) (a>0?a:-a)
#define Read(filename) freopen(filename, "r", stdin)


using namespace std;


int graph[26];
int kount;

int find(int i)
{
    if(graph[i] == i)
    {
        return i;
    }
    return graph[i] = find(graph[i]);
}



void join(int i, int j)
{
    int u = find(i);
    int v = find(j);
    if(u != v)
    {
        graph[u] = v;
        kount--;
    }
}


int main()
{
    int kases;
    bool blank = false;
    char top;
    string str;
    char c1, c2;
    int N;


    getint(kases);

    while(kases--)
    {
        if(blank)
        {
            printf("\n");
        }
        blank = true;


        cin>>top;
        N = top - 'A';
        kount = N + 1;

        loop(i, kount)
        {
            graph[i] = i;
        }

        cin.ignore();

        while(true)
        {
            getline(cin, str);
            if(str=="") break;
            c1 = str[0];
            c2 = str[1];
            join(c1 - 'A', c2 - 'A');
        }

        cout<<kount<<endl;





    }

    return 0;
}