Pagini recente » Cod sursa (job #2658900) | Cod sursa (job #95523) | Cod sursa (job #2976344) | Cod sursa (job #760480) | Cod sursa (job #913527)
Cod sursa(job #913527)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int maxn = 100005;
int num_vertices, num_edges, indecs;
vector<int> idx, low, graph[maxn], sol_aux, in_stack;
vector< vector<int> > sol;
stack<int> s;
int Minim(int a,int b)
{
if(a>b) return b;
return a;
}
void Read()
{
int aux1,aux2;
f>>num_vertices>>num_edges;
for(int i=1 ; i<=num_edges ; i++)
{
f>>aux1>>aux2;
graph[aux1].push_back(aux2);
}
f.close();
}
void Write()
{
g<<sol.size()<<'\n';
int i,j;
for(i=0;i<sol.size();i++)
{
for(j=0;j<sol[i].size();j++)
g<<sol[i][j]<<' ';
g<<'\n';
}
g.close();
}
void Tarjan(int v)
{
idx[v] = low[v] = indecs;
indecs++;
s.push(v);
in_stack[v] = 1;
vector<int>::iterator it;
for(it=graph[v].begin(); it!=graph[v].end(); ++it)
{
if(idx[*it] == -1)
{
Tarjan(*it);
low[v] = Minim(low[v],low[*it]);
}
else
if(in_stack[*it]==1)
low[v] = Minim(low[v],low[*it]);
}
if(low[v] == idx[v])
{
sol_aux.clear();
int node;
do{
node = s.top();
sol_aux.push_back(node);
in_stack[node]=0;
s.pop();
}while(v != node);
sol.push_back(sol_aux);
}
}
int main()
{
Read();
idx.resize(num_vertices+1), low.resize(num_vertices+1), in_stack.resize(num_vertices+1);
idx.assign(num_vertices+1, -1), in_stack.assign(num_vertices+1,0);
for(int i=1; i<=num_vertices; i++)
if(idx[i] == -1)
Tarjan(i);
Write();
return 0;
}