Cod sursa(job #1164527)

Utilizator UVS_Elfus_Deneo_KiraUVS-Elfus-Dutzul-Kira UVS_Elfus_Deneo_Kira Data 2 aprilie 2014 09:40:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<queue>
#define f cin
#define g cout
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define bit 20
#define inf (1<<30)
#define base 256
#define ba 255
#define N 200100
#define mod  1999999973
#define inu "ctc.in"
#define outu "ctc.out"
using namespace std;
ifstream f(inu);
ofstream g(outu);
//int dx[]={0,0,0,1,-1};
//int dy[]={0,1,-1,0,0};
vector<int> v[N],C[N],u[N];
stack <int> st;
int k,viz[N],n,m,nod,key,x,y,tc;
void dfs(int x)
{
    viz[x]=k;
    for(int i=0;i<v[x].size();++i)
    if(!viz[v[x][i]])
    dfs(v[x][i]);
    st.push(x);
}
void dfs1(int x)
{
    viz[x]=0;
    C[tc].pb(x);
    for(int i=0;i<u[x].size();++i)
    if(viz[u[x][i]]==key)
    dfs1(u[x][i]);
}
int main ()
{
    f>>n>>m;
    FOR(i,1,m)
    {
        f>>x>>y;
        v[x].pb(y);
        u[y].pb(x);
    }
    FOR(i,1,n)
    if(!viz[i])
    {
        ++k;
        dfs(i);
    }
    while(!st.empty())
    {
        while(!st.empty()&&!viz[st.top()])
        st.pop();
        if(st.empty())
        break;
        key=viz[st.top()];
        nod=st.top();
        st.pop();
        ++tc;
        dfs1(nod);
    }
    g<<tc<<"\n";
    FOR(i,1,tc)
    {
    FOR(j,0,C[i].size()-1)
    g<<C[i][j]<<" ";
    g<<"\n";
    }
    return 0;
}