Pagini recente » Cod sursa (job #1819213) | Cod sursa (job #1091554)
#include <cstdio>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int const N_MAX=100001;
//fstream fin("grader_test10.in", ios::in);
//fstream fout("grader_test10.out", ios::out);
vector <int> graph[N_MAX], graphT[N_MAX], comp[N_MAX], stock;
int k=0;
bool vizitat[N_MAX];
int N, M;
void citire()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int x, y;
scanf("%d", &N);
scanf("%d", &M);
for(int i=0; i<M; i++)
{
scanf("%d", &x);
scanf("%d", &y);
graph[x].push_back(y);
graphT[y].push_back(x);
}
}
void dfs1(int x)
{
vizitat[x]=true;
if(graphT[x].size() > 0)
{
//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.push_back(x);
}
void dfs2(int x)
{
vizitat[x]=true;
//for(unsigned int i=0; i<graph[x].size(); i++)
if(graph[x].size() > 0)
{
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(vector<int>::reverse_iterator it=stock.rbegin(); it!=stock.rend(); it++)
{
if(!vizitat[*it])
{
k++;
dfs2(*it);
}
}
printf("&d\n", k);
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++)
printf("%d ", *it);
printf("\n");
}
return 0;
}