Pagini recente » Cod sursa (job #825373) | Cod sursa (job #2943365) | Cod sursa (job #2602745) | Cod sursa (job #66671) | Cod sursa (job #2797156)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> listAux[100001];
vector<int> tareConexe[100001];
int nrTC=0;
bool cmp(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second > b.second);
}
class Graf{
public:
Graf(){}
void citire_dfs()
{
in>>m_nrNoduri>>m_nrMuchii;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
m_list[y].push_back(x);
}
}
void bfs()
{
in>>m_nrNoduri>>m_nrMuchii>>m_start;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
}
for(int i=1;i<=m_nrNoduri;i++)
{
m_viz[i]=2000000000;
}
m_viz[m_start]=0;
m_q[1]=m_start;
int p=1;
int u=1;
while(p<=u) //<=
{
int r=m_q[p];
for(int i=0;i<(m_list[r].size());i++)
{
int e=m_list[r][i];
// cout<<e<<' ';
if(m_viz[r]+1<m_viz[e])
{
m_viz[e]=m_viz[r]+1;
u++;
m_q[u]=e;
}
}
p++;
}
for(int i=1;i<=m_nrNoduri;i++)
{
if(m_viz[i]!=2000000000)
out<<m_viz[i]<<' ';
else
out<<"-1 ";
}
}
void r_dfs(int q)
{
m_viz[q]=1;
for(int i=0;i<m_list[q].size();i++)
{
int r=m_list[q][i];
if(m_viz[r]==0)
{
r_dfs(r);
}
}
m_stiva.push_back(q);
}
void rr_dfs(int q)
{
m_viz[q]=1;
for(int i=0;i<m_list[q].size();i++)
{
int r=m_list[q][i];
if(m_viz[r]==0)
{
rr_dfs(r);
}
}
tareConexe[nrTC].push_back(q);
}
void dfs()
{
in>>m_nrNoduri>>m_nrMuchii;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
m_list[y].push_back(x);
}
int s=0;
for(int i=1;i<=m_nrNoduri;i++)
{
if(m_viz[i]==0)
{
r_dfs(i);
s++;
}
}
r_dfs(1);
out<<s<<'\n';
}
void sorttop_recursie(int q)
{
int i;
m_viz[q]=1;
for(i=0;i<m_list[q].size();i++)
{
int t=m_list[q][i];
if(m_viz[t]==0)
{
sorttop_recursie(t);
}
}
m_aux++;
m_ordtop[m_aux]=q;
}
void sorttop()
{
int i;
in>>m_nrNoduri>>m_nrMuchii;
for(i=0;i<m_nrNoduri;i++)
{
m_grad.push_back(0);
m_ordtop.push_back(0);
}
for(i=1;i<=m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
m_grad[y]++;
}
for(i=1;i<=m_nrNoduri;i++)
{
if(m_grad[i]==0 && m_viz[i]==0)
{
sorttop_recursie(i);
}
}
//cout<<w<<'\n';
for(i=m_aux;i>0;i--)
{
out<<m_ordtop[i]<<' ';
}
}
void havelHakimi()
{
int s=0;
in>>m_nrNoduri;
for(int i=1;i<=m_nrNoduri;i++)
{
int x;
in>>x;
s+=x;
m_nodGrad.push_back(make_pair(i,x));
sort(m_nodGrad.begin(), m_nodGrad.end(),cmp);
}
if(s%2==0)
{
/*for(int i=0;i<m_nrNoduri;i++)
cout<<m_nodGrad[i].second;
cout<<'\n';
for(int i=0;i<m_nrNoduri;i++)
cout<<m_nodGrad[i].first;
cout<<"\n\n";*/
for(int i=1;i<=m_nrNoduri;i++)
{
if(m_nodGrad[i-1].second <= m_nrNoduri - i)
{
int aux = m_nodGrad[i-1].second;
for(int j = 1; j <= aux; j++)
{
m_nodGrad[i+j-1].second--;
m_nodGrad[i-1].second--;
m_list[m_nodGrad[i-1].first].push_back(m_nodGrad[i+j-1].first);
m_list[m_nodGrad[i+j-1].first].push_back(m_nodGrad[i-1].first);
}
}
else
{
out<<"-1";
return;
}
sort(m_nodGrad.begin()+i, m_nodGrad.end(),cmp);
/*for(int i=0;i<m_nrNoduri;i++)
cout<<m_nodGrad[i].second;
cout<<'\n';
for(int i=0;i<m_nrNoduri;i++)
cout<<m_nodGrad[i].first;
cout<<"\n\n";*/
}
int ok = 1;
for(int i=0;i<m_nrNoduri;i++)
{
if(m_nodGrad[i].second != 0)
ok = 0;
}
if(ok==1)
{
for(int i = 1; i <= m_nrNoduri; i++)
{
out<<i<<": ";
for(int j = 0; j < m_list[i].size(); j++)
{
out<<m_list[i][j]<<' ';
}
out<<'\n';
}
}
else
{
out<<"-1";
return;
}
}
else
{
out<<"-1";
return;
}
}
void ctc_Kosoraju()
{
in>>m_nrNoduri>>m_nrMuchii;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
listAux[y].push_back(x);
}
for(int i=1;i<=m_nrNoduri;i++)
{
if(m_viz[i]==0)
{
r_dfs(i);
}
}
for(int i=1;i<=m_nrNoduri;i++)
{
m_list[i].clear();
for(int j=0;j<listAux[i].size();j++)
{
m_list[i].push_back(listAux[i][j]);
}
}
/*for(int i=1;i<=m_nrNoduri;i++)
{
cout<<i<<": ";
for(int j=0;j<listAux[i].size();j++)
{
cout<<m_list[i][j]<<' ';
}
cout<<'\n';
}*/
for(int i=0; i<=m_nrNoduri;i++)
m_viz[i]=0;
for(int i=m_stiva.size()-1;i>=0;i--)
{
if(m_viz[m_stiva[i]]==0)
{
nrTC++;
rr_dfs(m_stiva[i]);
}
}
out<<nrTC<<'\n';
for(int i = 1; i <= nrTC; i++)
{
for(int j = 0; j < tareConexe[i].size();j++)
out<<tareConexe[i][j]<<' ';
out<<'\n';
}
}
private:
int m_nrMuchii;
int m_nrNoduri;
int m_start;
int m_viz[100001];
int m_q[100001];
vector<int> m_ordtop;
vector<int> m_grad;
vector<int> m_stiva;
vector<pair<int,int>> m_nodGrad;
int m_aux;
vector<int> m_list[100001];
};
int main() {
Graf graf;
graf.ctc_Kosoraju();
}