Pagini recente » Cod sursa (job #1471686) | Cod sursa (job #1253420) | Cod sursa (job #404971) | Cod sursa (job #2840597) | Cod sursa (job #1068991)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#define Nmax 100000
#define Mmax 200000
using namespace std;
unsigned n,m,current_time;
vector<vector<unsigned> > graf, graf_rev,solutie;
vector<unsigned> time,is_visited,time_rev;
stack<unsigned> coada;
void DFS_Rev(unsigned start_node)
{
unsigned len,i;
is_visited[start_node]=1;
len = graf_rev[start_node].size();
for(i=0; i<len;i++)
if(!is_visited[graf_rev[start_node][i]])
DFS_Rev(graf_rev[start_node][i]);
time[start_node] = ++current_time;
}
void time_table()
{
int i;
current_time=0;
for(i=n;i>0;i--)
{
if(is_visited[i]==0){
DFS_Rev(i);
}
}
}
void DFS(unsigned start_node)
{
unsigned len,i;
is_visited[start_node]=1;
len = graf[start_node].size();
for(i=0; i<len;i++)
if(!is_visited[graf[start_node][i]])
DFS(graf[start_node][i]);
time.push_back(start_node);
}
void find_dag()
{
int i;
for(i=n;i>0;i--)
{
if(is_visited[time_rev[i]]==0){
time.clear();
DFS(time_rev[i]);
solutie.push_back(time);
}
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
unsigned i,j,u,v,len;
//citire
f>>n>>m;
graf.resize(n+1);graf_rev.resize(n+1);time.resize(n+1);is_visited.resize(n+1);
for(i=1;i<=m;i++)
{
f>>u>>v;
graf[u].push_back(v);
graf_rev[v].push_back(u);
}
time_table();
time_rev.resize(n+1);
for(i=1;i<=n;i++)
{
time_rev[time[i]] = i;
}
is_visited.clear();is_visited.resize(n+1);
find_dag();
unsigned solutie_size = solutie.size();
g<<solutie_size<<'\n';
for(i=0;i<solutie_size;i++)
{
len = solutie[i].size();
sort(solutie[i].begin(), solutie[i].end());
for(j=0;j<len;j++)
g<<solutie[i][j]<<' ';
g<<'\n';
}
return 0;
}