Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/h0pzy | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1091364)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int const N_MAX=100001;
fstream fin("grader_test1.in", ios::in);
fstream fout("grader_test1.out", ios::out);
vector <int> graph[N_MAX], graphT[N_MAX], comp[N_MAX];
int k=0, stock[N_MAX];
bool vizitat[N_MAX];
int N, M;
void citire()
{
int x, y;
fin>>N;
fin>>M;
for(int i=0; i<M; i++)
{
fin>>x>>y;
graph[x].push_back(y);
graphT[y].push_back(x);
}
}
void dfs1(int x)
{
vizitat[x]=true;
int start=*(graphT[x].begin());
int finish=*(graphT[x].end());
//for(unsigned int i=0; i<graphT[x].size(); i++)
for(vector<int>::iterator it=graphT[x].begin(); it!=graphT[x].end(); it++)
{
int current=*it;
if(!vizitat[current])
dfs1(current);
}
stock[0]++;
stock[stock[0]]=x;
}
void dfs2(int x)
{
vizitat[x]=true;
//for(unsigned int i=0; i<graph[x].size(); i++)
for(vector<int>::iterator it=graph[x].begin(); it!=graph[x].end(); it++)
{
if(!vizitat[*it])
dfs2(*it);
}
comp[k].push_back(x);
}
void SortareTop()
{
for(int i=1; i<=N; i++)
if(!vizitat[i])
dfs1(i);
}
int main()
{
citire();
SortareTop();
memset(vizitat, false, sizeof(vizitat));
for(int i=N; i>0; i--)
{
if(!vizitat[stock[i]])
{
k++;
dfs2(stock[i]);
}
}
fout<<k<<endl;
for(int i=1; i<=k; i++)
{
//for(unsigned int j=0; j<comp[i].size(); j++)
for(vector<int>::iterator it=comp[i].begin(); it!=comp[i].end(); it++)
fout<<(*it)<<" ";
fout<<endl;
}
return 0;
}