Cod sursa(job #1261757)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 12 noiembrie 2014 17:44:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=100000;
vector<int>g[N+1],h[N+1],ctc[N+1];
queue<int>q;
stack<int>st;
bool vis[N+1];
int n,m;
void dfs(int dad){
    vis[dad]=true;
    for(int i=0;i<g[dad].size();i++){
        int son=g[dad][i];
        if(!vis[son])
            dfs(son);
    }
    st.push(dad);
}
void bfs(int node,int k){
    q.push(node);
    vis[node]=true;
    while(!q.empty()){
        int dad=q.front();
        for(int i=0;i<h[dad].size();i++){
            int son=h[dad][i];
            if(!vis[son]){
                vis[son]=true;
                q.push(son);
            }
        }
        ctc[k].push_back(dad);
        q.pop();
    }
}
int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        h[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(i);
    int res=0;
    memset(vis,0,sizeof(vis));
    while(!st.empty()){
        if(!vis[st.top()])
            bfs(st.top(),++res);
        st.pop();
    }
    printf("%d\n",res);
    for(int i=1;i<=res;i++){
        for(int j=0;j<ctc[i].size();j++)
            printf("%d ",ctc[i][j]);
        printf("\n");
    }
    return 0;
}