Pagini recente » Cod sursa (job #2058104) | Cod sursa (job #63428) | Cod sursa (job #520170) | Cod sursa (job #1744548) | Cod sursa (job #848047)
Cod sursa(job #848047)
#include<fstream>
#include<bitset>
#include<vector>
#include<stack>
#define NMAX 100002
#define MMAX 200002
using namespace std;
int n,m,nr;
int lowl[NMAX],level[NMAX];
vector <int> v[NMAX],comp[NMAX];
stack <int> S;
bitset <NMAX> viz;
ifstream in("ctc.in");
ofstream out("ctc.out");
void scan() {
int a,b;
in>>n>>m;
for (int i=1;i<=m;i++)
{
in>>a>>b;
v[a].push_back(b);
}
}
inline int min(int a,int b)
{
if (a<=b)
return a;
return b;
}
void componenta(int nod)
{
int a;
nr++;
while (S.top()!=nod)
{
a=S.top();
comp[nr].push_back(a);
viz[a]=false;
S.pop();
}
comp[nr].push_back(nod);
viz[nod]=false;
S.pop();
}
void dfs(int nod,int nivel)
{
level[nod]=nivel;
lowl[nod]=nivel;
viz[nod]=true;
S.push(nod);
for (vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
{
if (!level[*it])
{
dfs(*it,nivel+1);
lowl[nod]=min(lowl[nod],lowl[*it]);
}
else if (viz[*it]==true)
lowl[nod]=min(lowl[nod],lowl[*it]);
}
if (lowl[nod]==level[nod])
componenta(nod);
}
void print()
{
out<<nr<<"\n";
for (int i=1;i<=nr;i++)
{
for (vector<int>::iterator it=comp[i].end()-1;it>=comp[i].begin();it--)
out<<*it<<" ";
out<<"\n";
}
}
int main() {
scan();
for (int i=1;i<=n;i++)
{
if (!level[i]) dfs(i,1);
}
print();
return 0;
}