Pagini recente » Cod sursa (job #1331826) | Cod sursa (job #1599679) | Cod sursa (job #1826294) | Cod sursa (job #342777) | Cod sursa (job #936636)
Cod sursa(job #936636)
///componente tare conexe
#include<fstream>
#include<vector>
#include<stack>
#include<cstring>
#define In "ctc.in"
#define Out "ctc.out"
#define Nmax 100001
using namespace std;
int n,nr;
bool viz[Nmax];
stack< int >St;
vector< int >graf[Nmax];
vector< int >graf_t[Nmax];
vector< int > sol[Nmax];
//graf_t = graf transpus
inline void Citire()
{
int m,x,y;
ifstream f(In);
f>>n>>m;
while(m--)
{
f>>x>>y;
graf[x].push_back(y);
graf_t[y].push_back(x);
}
f.close();
}
inline void Dfs(int nod)
{
viz[nod] = true;
St.push(nod);
for(vector<int>::iterator it = graf[nod].begin();it!=graf[nod].end();it++)
if(viz[*it]==false)
Dfs(*it);
}
inline void Parcurgere_adancime()
{
for(int i=1;i<=n;i++)
if(viz[i]==false)
Dfs(i);
}
inline void Dfs_t(int nod)
{
viz[nod] = true;
sol[nr].push_back(nod);
for(vector<int>::iterator it = graf_t[nod].begin();it!=graf_t[nod].end();it++)
if(viz[*it]==false)
Dfs_t(*it);
}
inline void Parcurgere_adancime_t()
{
memset(viz,0,sizeof(viz));
while(!St.empty())
{
if(viz[St.top()]==false)
{
nr++;
Dfs_t(St.top());
}
St.pop();
}
}
inline void Afisare()
{
ofstream g(Out);
g<<nr<<"\n";
vector < int >::iterator it;
for(int i=1;i<=nr;i++)
{
for(it=sol[i].begin();it!=sol[i].end();it++)
g<<*it<<" ";
g<<"\n";
}
g.close();
}
int main()
{
Citire();
Parcurgere_adancime();
Parcurgere_adancime_t();
Afisare();
return 0;
}