Pagini recente » Solutii FMI No Stress 4 | Cod sursa (job #3246856) | Cod sursa (job #3148540) | Cod sursa (job #3041631) | Cod sursa (job #681760)
Cod sursa(job #681760)
//
// main.cpp
// ctc3
//
// Created by Nenu Adrian on 2/17/12.
// Copyright 2012 __MyCompanyName__. All rights reserved.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> G[100100],GT[100100],A,S[100100];
int sol,nr,t[100100],viz[100100];
void df(int nod){
viz[nod]=1;
int i;
for (i=0; i < G[nod].size();i++){
if(!viz[G[nod][i]])
df(G[nod][i]);
}
t[nod]=++nr;
}
void dff(int nod){
viz[nod]=1;
S[sol].push_back(nod);
int i;
for (i=0; i < GT[nod].size();i++){
if(!viz[GT[nod][i]])
dff(GT[nod][i]);
}
}
inline bool cmp(int a, int b){
return (t[a]>t[b]);
}
int main(){
int i,x,y,n,m,j;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!viz[i])
df(i);
for(i=1;i<=n;i++){
viz[i]=0;
A.push_back(i);
}
sort(A.begin(), A.end(), cmp);
for(i=0;i<n;i++)
if(!viz[A[i]])
{
sol++;
dff(A[i]);
}
g<<sol<<endl;
for(i=1;i<=sol;i++){
for(j=0;j<S[i].size();j++)
g<<S[i][j]<<" ";
g<<endl;}
}