Pagini recente » Cod sursa (job #1073067) | Cod sursa (job #2553145) | Cod sursa (job #2253400) | Cod sursa (job #337621) | Cod sursa (job #989484)
Cod sursa(job #989484)
#include<fstream>
#include<list>
#define dmax 100003
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, sccNr;
list<list<int> >scc;
list<list<int> >::iterator it;
list<int>currentScc;
list<int>::iterator ir;
list<int>adj[dmax];
list<int>adjT[dmax];
list<int>sorted;
bool visited[dmax];
void dfs(int currentN)
{
list<int>::iterator it;
for(it = adj[currentN].begin(); it != adj[currentN].end(); it++)
{
if(visited[*it] == false)
{
visited[*it] = true;
dfs(*it);
}
}
sorted.push_front(currentN);
}
void dfsT(int currentN)
{
list<int>::iterator it;
currentScc.push_back(currentN);
for(it = adjT[currentN].begin(); it != adjT[currentN].end(); it++)
{
if(visited[*it] == false)
{
visited[*it] = true;
dfsT(*it);
}
}
}
int main()
{
in>>n>>m;
for(int i=1; i<=m; i++)
{
int a, b;
in>>a>>b;
adj[a].push_back(b);
adjT[b].push_back(a);
}
in.close();
for(int i=1; i<=n; i++)
{
visited[i] = false;
}
for(int i=1; i<=n; i++)
{
if(visited[i] == false)
{
visited[i] = true;
dfs(i);
}
}
for(int i=1; i<=n; i++)
visited[i] = false;
for(ir = sorted.begin(); ir != sorted.end(); ir++)
{
if(visited[*ir] == false)
{
if(!currentScc.empty())
{
sccNr++;
scc.push_back(currentScc);
currentScc.clear();
}
visited[*ir] = true;
dfsT(*ir);
}
}
if(!currentScc.empty())
{
sccNr++;
scc.push_back(currentScc);
currentScc.clear();
}
out<<sccNr<<'\n';
for(it = scc.begin(); it != scc.end(); it++)
{
for(ir = (*it).begin(); ir != (*it).end(); ir++)
out<<*ir<<" ";
out<<'\n';
}
out.close();
return 0;
}