Pagini recente » Cod sursa (job #1036915) | Cod sursa (job #3185995) | Cod sursa (job #2195510) | Cod sursa (job #1436178) | Cod sursa (job #912441)
Cod sursa(job #912441)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int maxn = 200001;
int num_vertices,num_edges,index,num_ctc;
int ind[maxn],in_stack[maxn],low[maxn];
vector<int> graph[maxn],con[maxn];
stack<int> s;
int Minim(int a,int b)
{
if(a>b) return b;
return a;
}
void StrongConnect(int v)
{
ind[v] = index;
low[v] = index;
index++;
s.push(v);
in_stack[v]=1;
vector<int>::iterator it;
for(it=graph[v].begin(); it!=graph[v].end(); it++)
if(!ind[*it])
{
StrongConnect(*it);
low[v] = Minim(low[v],low[*it]);
}
else
if(in_stack[*it])
low[v] = Minim(low[v],ind[*it]);
if(ind[v]==low[v])
{
num_ctc++;
int node;
do{
node = s.top();
s.pop();
in_stack[node]=0;
con[num_ctc].push_back(node);
}while(node!=v);
}
}
int main()
{
int i,aux1,aux2;
vector<int>::iterator it;
f>>num_vertices>>num_edges;
for(i=1;i<=num_edges;i++)
{
f>>aux1>>aux2;
graph[aux1].push_back(aux2);
}
for(i=1;i<=num_vertices;i++)
if(!ind[i])
StrongConnect(i);
g<<num_ctc<<'\n';
for(i=1;i<=num_ctc;i++)
{
for(it=con[i].begin();it!=con[i].end();it++)
g<<*it<<' ';
g<<'\n';
}
/*
for(i=1;i<=num_vertices;i++)
g<<ind[i]<<' ';
g<<'\n';
for(i=1;i<=num_vertices;i++)
g<<low[i]<<' ';
g<<'\n';*/
return 0;
}